The construction/destruction order of global variables is undefined (unspecified?) in C++. There are many threads in this forum about people encountering strange crashes because they made their RenderWindows or resource classes global, and there's simply nothing SFML can do to prevent such crashes.
More importantly, globals are usually evil anyway, and there's no reason why your texture map needs to be global. Simply construct it in main() and pass it to whoever needs it, like any other major dependency or subsystem. But aside from the "global" thing, what you said sounds right to me: A simple std::map does the job fine as long as it's not global.
@kim366: To directly answer your original question, it's probably because std::vector is allowed to move/copy its elements around. Normally this is fine, but here you have a vector of objects that contain pointers to the objects in another vector, so that's pretty much guaranteed to break (which is not in any way unique to SFML). A "stable" container like a std::map will not move its elements around, which is why it's the simplest way to solve this problem.