As long as the allocation and deallocation of the memory are properly protected and you also ensure that the structures are only accessed while they are under the same mutex, I can't really see this being a problem. Please note that this goes for read and write access, not only for write access as you need to ensure that the structure stays where it is while someone's reading data from it.
Is there are chance that some code somewhere attempts to access these data structures outside mutex protection? Or worse could there be a chance that some of these structures fall victim to C++ object lifetime considerations (say, they're being destroyed because they're referenced via boost::shared_ptrs and the last shared_ptr has just exited the building?
Are you 100% sure that it is memory corruption? Another bug that looks very similar is when some code holds onto a reference that it shouldn't and the referenced object gets moved due to memory reallocation. This isn't such an outlandish scenario as adding another element to a vector can trigger that (just to give an example).