Thread: Strange windows STL crashing problem

I am suffering from a random crashing problem on win64 that results in the following stack trace.
My code is heavily threaded, and the crash always occurs inside the MS STL library (VC++ 8), and sometimes in different places, but usually in something that appears to be allocating memory. I can find out which function from the MAP file, but the crashing code is sometimes as simple as construction of a zero length std::string.
The crashing code is all fully reentrant, and none of the variables are shared between threads.
Does anyone have any idea what may cause such behaviour?
I have run the same program with several years uptime on a number of UNIX boxes, and through heap profiler, valgrind, with no issues.
Am I running out of stack space because of too many threads?
Also, I have checked the program in 'process explorer' to make sure that it is not leaking handles.
Any insight would be much appreciated.

# Child-SP RetAddr Call Site
00 00000000`02d19488 00000000`77d704bf ntdll!ZwWaitForSingleObject+0xa
01 00000000`02d19490 000007ff`6e017d66 kernel32!WaitForSingleObjectEx+0xdf
02 00000000`02d19530 000007ff`6e007507 faultrep!ReportEREvent+0x2306
03 00000000`02d195e0 000007ff`6e00b05d faultrep!ReportHang+0x27c7
04 00000000`02d1dab0 00000000`77dc01f6 faultrep!ReportFault+0x3ed
05 00000000`02d1e950 00000000`77dbc2df kernel32!UnhandledExceptionFilter+0x606
06 00000000`02d1ed40 00000000`77ee6583 kernel32!SetThreadStackGuarantee+0x1cf
07 00000000`02d1ed70 00000000`77ee455d ntdll!RtlUnwindEx+0x213
08 00000000`02d1ee00 00000000`77ee6097 ntdll!RtlSizeHeap+0x7d
09 00000000`02d1ee30 00000000`77ef31dd ntdll!RtlLookupFunctionEntry+0x607
0a 00000000`02d1f4e0 00000000`7c426b8a ntdll!KiUserExceptionDispatcher+0x2d
0b 00000000`02d1fa80 00000000`7c4294d9 msvcp80!std::basic_string<char,std::char_traits<ch ar>,std::allocator<char> >::assign+0x1a
0c 00000000`02d1fab0 00000001`40087ef1 msvcp80!std::basic_string<char,std::char_traits<ch ar>,std::allocator<char> >::basic_string<char,std::char_traits<char>,std::a llocator<char> >+0x29
0d 00000000`02d1fae0 00000001`4008db80 progrel!progrel+0x49c61
0e 00000000`02d1fc20 00000000`781337d7 progrel!lprogrel+0x4f8f0
0f 00000000`02d1ff20 00000000`78133894 msvcr80!endthreadex+0x47
10 00000000`02d1ff50 00000000`77d6b6da msvcr80!endthreadex+0x104
11 00000000`02d1ff80 00000000`00000000 kernel32!BaseThreadStart+0x3a

...
msvcp80!std::basic_string<char,std::char_traits<ch ar>,std::allocator<char> >::assign:
00000000`7c426b70 48895c2408 mov qword ptr [rsp+8],rbx
00000000`7c426b75 48896c2410 mov qword ptr [rsp+10h],rbp
00000000`7c426b7a 4889742418 mov qword ptr [rsp+18h],rsi
00000000`7c426b7f 48897c2420 mov qword ptr [rsp+20h],rdi
00000000`7c426b84 4154 push r12
00000000`7c426b86 4883ec20 sub rsp,20h
00000000`7c426b8a 4c394218 cmp qword ptr [rdx+18h],r8 ---------------------------------- FAULT
00000000`7c426b8e 4d8be1 mov r12,r9
00000000`7c426b91 498be8 mov rbp,r8
00000000`7c426b94 488bf2 mov rsi,rdx
00000000`7c426b97 488bd9 mov rbx,rcx
00000000`7c426b9a 7305 jae msvcp80!std::basic_string<char,std::char_traits<ch ar>,std::allocator<char> >::assign+0x31 (00000000`7c426ba1)
00000000`7c426b9c e87fb10700 call msvcp80!std::_String_base::_Xran (00000000`7c4a1d20)
00000000`7c426ba1 488b7e18 mov rdi,qword ptr [rsi+18h]
00000000`7c426ba5 482bfd sub rdi,rbp
00000000`7c426ba8 4c3be7 cmp r12,rdi
00000000`7c426bab 490f42fc cmovb rdi,r12
...

The problem doesn't _appear_ to occur on win32.

Yes, the program did throw std::bad_alloc when i did try putting common lines that core dump inside try / catch blocks. It usually crashes in the same places, all where memory is allocated inside a worker thread, but not always.
Sometimes it also crashes with win32 calls failing, almost always EnterCriticalSection() (throwing RTL exception) (I did remember to InitializeCriticalSection())
Using CreateMutex() avoids the above crashes (since I guess resources are pre-allocated?), but it doesn't seem like a good solution.

It occurs on every one node of an identical cluster of 64-bit machines with 4Gb of RAM each (most of which is free) + 2x dual core CPUs. The process also doesn't appear to be leaking memory (RSS is still tiny, and remains fairly constant over time).
The machines can be very heavily loaded (running CFD software), but the memory requirements are actually fairly modest.
It can take considerably time to reproduce this. It happens maybe once/day usually when the program is running a few worker threads (thread count <20, so not excessive). Very frustrating...

Sorry, I didn't make clear, CreateMutex() only solves the crashing on entry to critical sections. The STL crashing is still an issue.
Address space fragmentation was certainly one of my thoughts initially, but I am skeptical that this should be an issue in a 64-bit process that is actually allocating very little memory. I shall look into this anyway.

I have a very similar problem. I have a C++ DLL which compiles and runs OK in 32-bit mode. It also runs OK in 64-bit mode when compiled with Visual C++ 2005. When compiled in Release mode with Visual C++ 2008, it crashes. The first crash point I found was when an item was being inserted into a std::map (this was the first item to be added.) I tried replacing the std::map with a class I wrote myself, and then the program crashed in another location where a value was being extracted from another std::map.