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.
Optimizations are good... but I'd never expect a 50% gain in performance with them.
I would assume so too, but it's worth ruling out.
I'm slightly confused by the invocation of gcc.
gcc -m32 -O2 -fomit-frame-pointer -mtune=k8 -march=k8 mersenne.c /usr/local/lib/gmp.so
Adding the path to gmp.so, in particular. If my understanding of the gcc documentation is accurate, it will regard gmp.so as an "in file", which would seem to imply (if gcc is not complaining) that gmp.so is being statically linked with your executable. You can test this by running ldd yourbinary. If you don't see gmp.so in the output, you're statically linking. I'm not well versed on VC++, so I don't know if your VC++ build is performing static linking or how you would check on Windows. Can anyone chime in?
Back to the point at hand though, if this was the case you should have a fixed delay since dynamic linking resolution is done at invocation and the runtime differences would always be different by a roughly fixed amount.