Perhaps gcc is performing optimizations that VC++ is not. Try compiling them both with no optimizations and test the run times. If they're equivalent, then gcc is optimizing more aggressively, otherwise the culprit is elsewhere.
It would be difficult to compile my program with no optimizations in GCC, as GMP's make script automatically compiles GMP with the most optimal compiler flags available while Visual Studio will recompile GMP as a debug build if I was to try to compile my program
in debug mode. That prevents a fair comparsion with optimizations disabled.