How is that possible?
When an exception is thrown, control passes to __cxa_throw routine (usually in libstdc++.so), which is then responsible for finding the catch clause and calling destructors along the way, or calling std::terminate if no catch is found.
The answer then is most likely that the first executable (the one where exceptions work) uses libstdc++.so that is capable of decoding .eh_frame in your library, while the second application (the one where exceptions do not work), either uses an older (incompatible) version of libstdc++.so, or links against libstdc++.a, or something along these lines.
Note: the actual work of raising the exception is done by _Unwind_RaiseException in libgcc_s.so.1, so even if both applications use the same libstdc++.so, they may still use different libgcc.
Update:
Will I benefit from static linking libstdc++ and libgcc into my .so library?
Maybe. TL;DR: it's complicated.
There are a few things to consider:
On any platform other than i386, you would have to build your own copy of libstdc++.a and libgcc.a with -fPIC before you can link them into your zzz.so. Normally these libraries are built without -fPIC, and can't be statically linked into any .so.
Static linking of libstdc++.a into your zzz.so may make it a derived work, and subject to GPL (consult your lawyer).
Even when there is a _Unwind_RaiseException exported from zzz.so, normally there will already be another instance of _Unwind_RaiseException defined in (loaded earlier) libgcc_s.so, and that earlier instance is the one that will be called, rendering your workaround ineffective. To make sure that your copy of _Unwind_RaiseException is called, you would need to link zzz.so with -Bsymbolic, or with a special linker script to make all calls to _Unwind_RaiseException (and everything else from libgcc.a) internal.
Your workaround may fix the problem for zzz.so, but may cause a problem for unrelated yyy.so that is loaded even later, and that wants the system-provided _Unwind_RaiseException, not the one from zzz.so. This is another argument for hiding all libgcc.a symbols and making them internal to zzz.so.
So the short answer is: such workaround is somewhat likely to cause you a lot of pain.