I went about adding mutexes all around my code last night to make any access to an STL container thread safe. It went totally smoothly and I only caused one accidental deadlock by putting a release mutex inside of a conditional instead of outside. Easily fixed and tested. Adding all this safety in the engine was really easy to do and my perf hit is negligable. It's so rare that 2 threads would be trying to access the same container but it's worth the piece of mind. In the end this addition is great.
After I got all the mutexes in and working correctly I started trying to get the random crash and sure enough I did!! Annoying but at least it let me know it wasn't an STL bug. After that I decided to try and do some more memory debugging to see if I was getting any weird overwriting. Once again using MMGR from Fluid I started running through things. I was seeing weird behaviour where back to back runs weren't giving me the same results so I switched my engine to single thread mode and everything started going smoothly. After letting the game run with all the hard core memory flags on I hit pay dirt! When I was loading a texture of all things I was getting some weird under and overflow issues. The only problem is that I use the stock D3DX texture loading routines so I don't have code for them and I didn't change anything into them.
After figuring out something was going wacky in textures my mind jumped to the possibility that I had a malformed texture file or something, which in turn reminded me that a couple of weeks ago I converted some of my textures from pngs to dds files using the DX texture compression tool that comes with the DXSDK. I quickly switched those files back to their png version and bingo bango bongo no more crashing!!!!
I still have no idea why those files are really causing the crash. The only thing I can think of is that there is something deep in the bowels of d3dx.lib that is not thread safe when loading compressed textures. Either way I have a solution to my horrible bug!! I can now enjoy the weekend and not have to kick any puppies!