My previous post on a possible GCC bug is almost certainly a GCC bug. It turns out this is basically expected behavior of the GCC visibility feature. However, as this wiki page on visibility describes: "When exceptions start mysteriously malfunctioning, the cause is exactly this one!". Read the section named "Problems with C++ exceptions (please read!)". Here's the juicy bits:

The obvious first step is to mark all types throwable across shared object boundaries always as default visibility. [ ... ] You must do this because even if (e.g.) the exception type's implementation code lives in DLL A, when DLL B throws an instance of that type, the catch handler in DLL C will look for the typeinfo in DLL B.

However, this isn't the full story - it gets harder. [ ... ] The upshot of this is that if you forget your preprocessor defines in just one object file, or if at any time a throwable type is not declared explicitly public, the -fvisibility=hidden will cause it to be marked hidden in that object file which causes the typeinfo to vanish in the outputted binary (which then causes any throws of that type to cause terminate() to be called in the catching binary).

Sure enough, looking at the <stdexcept> header file, std::out_of_range is not declared as public. Contrast this with the <exception> header file which is surrounded with: 

#pragma GCC visibility push(default)
#pragma GCC visibility pop

I have filed GCC Bug #26217. Oh, and be very careful when declaring your exception classes!

Update (14-Feb-2006): The GCC bug has been closed as a duplicate of #19664 (which has been open for a year, and is targeted only for 4.2). Apparently they're working on a higher-level fix, yet it's currently still broken in 4.0 and 4.1. It's not my project, but I'd release the band-aid that fixes some problems until the overall fix is complete. Also, someone from Apple posted about the problem (with a patch) back in December, and was met with the same response.