msbuild has the ability to run an internal version of nuget restore via a t:Restore command line argument. For example: msbuild t:Restore xxx.sln. More information can be found here
I have a number of solutions that restore their nuget content successfully with this msbuild feature, but not when using the nuget restore action, even after referencing a number of different version of nuget.exe.