It happened because the VS2008 redistributables aren't installed with Windows. They must be installed by another application, which means they won't be present on virgin Windows installations. But they're likely to be present on machines which have had a few applications installed since many Windows apps use them. Native Windows applications such as Notepad don't depend on them, so it's not surprising Notepad runs without them.
As typ1232 already pointed out, the /MT option will solve your problem (at the expense of increasing your EXE and DLL sizes). The libraries for native Windows APIs are guaranteed to be present unless they're specifically documented as being an option you must install separately, so you don't need to worry about them.
Testing applications with a release mode build on virgin Windows installations is a crucial step in testing any Windows application, as you've now discovered.