OpenMP is a compiler runtime thing and not a platform thing.
ie. If you compile your app using Visual Studio 2005 or higher, then you always have OpenMP available as the runtime supports it. (and if the end-user doesn't have the Visual Studio C runtime installed, then your app won't work at all).
So, you don't need to worry, if you can use it, it will always be there just like functions such as strcmp. To make sure they have the CRT, then you can install the visual studio redistributable.
edit:
ok, but GCC 4.1 will not be able to compile your openMP app, so the issue is not the target machine, but the target compiler. As all compilers have pre-defined macros giving their version, wrap your OpenMP calls with #ifdef blocks. for example, GCC uses 3 macros to identify the compiler version, __GNUC__, __GNUC_MINOR__ and __GNUC_PATCHLEVEL__