Surprising. Most of these should add nothing or next to nothing in my opinion, unless you really enforce it by using ultra-fat components of libstdc++. user32, kernel32, or msvcrt for example will only add some thunks for functions that your program actually uses, that's a few bytes for a small program (8 bytes per thunk unless you force alignment to be more than that), and maybe a kilobyte or two top for pretty much every program. libstdc++ can certainly add a few hundred kilobytes, but only if you actually use the stuff (and then it's not surprising).
I've just looked what the unit test program to one of my containers compiles to, as that's pretty much the smallest non-helloworld project I have at hand. Gcc 4.4.0-tdm turns roughly 10 kB of sources (not counting system headers) into a 8.5 kB object file, and this into a 33 kB executable. That includes around 7 kB for the main program using std::vector, and 1 kB for exception handling. It takes well under a second to compile and link. Gcc 4.4.1-tdm produces considerably larger executables, though I don't have it installed now, so can't tell for this example.
Well, whichever it is, you're probably right insofar as we'll not likely be able to tell why wilcomir's executables are that big.