It's not clear that this problem can be overcome, especially in the context of shared libraries. To solve it, the shared library loader must be able to deduce the dependency between static objects, which is almost impossible considering that dependencies can arise after multiple levels of indirect function calls--especially virtual functions calls whose targets cannot be known at load time.
Because you can't count on things to work at static constructor time unless they are specifically documented to do so--and most should not make that promise--avoid exporting static objects as part of an interface that can be called from static object constructors (this is also important for performance reasons, as described earlier). For more information, see "Avoid static objects" on page 86.
NOTE The Annotated C++ Reference Manual (Stroustrup) discusses a technique (not based on static objects) that achieves much of the same benefit as static objects but doesn't suffer from this problem. Read xa4 3.4, "Start and Termination," if you are thinking about exporting static objects to clients.