that's an incredible margin, and sounds suspiciously like they didn't enable optimizations on gcc, or set icc to optimize for a specific processor and gcc to generic, or something like that.
At which point, its not just the compiler (which GCC is pretty good at), but also the threading implementation (which I can believe that GCC has an inferior Windows-threading OpenMP implementation).
I don't really use either tool. But OpenMP + GCC on Windows doesn't sound like it'd be fast to me.
--------
MSVC only has OpenMP 2.0 support (OpenMP is all the way up to 5.0 now).
OpenMP, despite being a common interface, also is pretty reliant on many implementation details for performance. One way of doing things on GCC could be faster than another, while it could be the opposite on ICC. Its quite possible that their codebase is tailored for ICC, and that recompiling it under GCC (with a different OpenMP implementation) results in weaker performance.
I wouldn't expect 250% performance difference in normal code however. GCC and ICC aren't that far off under typical circumstances.