First off, this requirement exists for both 32-bit and 64-bit code. You're just a bit more likely to be lucky with 32-bit code and somebody else having it installed before you. As it was on your dev machine by the VS installer.
It is induced by a compiler setting. Project + Properties, C/C++, Code Generation, Runtime Library setting. All the project templates in VS have this setting at /MD. You can change it to /MT and no longer have a dependency on the runtime DLLs, like msvcr90.dll. The runtime library code will be linked into your program instead of relying on the DLLs to be present on the target machine.
You have to be careful however, the /MD setting is the safe setting. It ensures that you won't get into trouble when you create your own DLLs and write code that returns C++ objects (like std::string) or pointers that must be released by the caller. This won't work well if the DLL and the EXE each have their own copy of the CRT linked into them. They will use different heaps, releasing a pointer across heaps cannot work properly. A silent leak on XP, a crash on Vista and up.
The redistributable .exe is actually meant as a downloadable installer that your customer can use when you forget to write an installer for your program. The much better solution is for you to write an installer that gets everything copied and installed properly. It takes less than a minute to make one. Add a Setup and Deployment + Setup project to your solution. Right-click it, Add, Project Output. Project + Properties, Prerequisites and tick the "Visual C++ Runtime Libraries (x64)" checkbox. If you prefer to create your own installer then you can use the merge modules in C:\Program Files (x86)\Common Files\Merge Modules
Oh, and deploy the Release build, not the Debug build. The debug version of the CRT is not distributable.
