stdext::hash_map dies at erase, but only in with /O2 + /MTd

It seems that when I do
   stdext::hash_map< std::string, int > map;
   ...
   map.erase( key )

it occassionally fails, shouting: "ITERATOR LIST CORRUPTED!"
at xutility:178

I've isolated it in a couple of examples below. It only seems to fail if I
use both "/O2" "/MTd" together at the command line.
Sadly, I can't do without either since,
- I need debugging
- apps run much too slow without optimization

Am I using this wrong? Can anyone recommend a workaround.
I expect std::map<consoleString, int> to be too slow since:
- the map is quite big (>4000)
- most of the strings have similar prefixes meaning that (s1<s2) tests
compare
   most of the string.

I'm using VC++ Express 8.

- Stu

-- small example

#include <hash_map>
typedef stdext::hash_map< std::string, int > stringToIntMap;

   if ( 1 )
   {
      std::string key1 = "ya ya ya ya ya ya ya ya ya ya ya ya ";
      std::string key2 = "yak yak yak yak yak yak yak ";
      stringToIntMap map;
      map[ key1 ] = 1;
      map[ key2 ] = 2;
      map.erase( key1 );
      map.erase( key2 ); // CRASH!
   }

-- big example
#include <vector>
#include <string>
#include <algorithm>
#include <assert.h>

// Fails /O2 + /MTd combo seems to be the problem
#include <hash_map>
typedef stdext::hash_map< std::string, int > stringToIntMap;

// Works fine...
//#include <map>
//typedef std::map< std::string, int > stringToIntMap;

// Make a string of random characters
static std::string randomString( int size )
{
   std::string s;
   s.resize( size );
   for ( int i=0; i<size; i++ )
   {
      char c = 32 + char( rand()%(127-32) );
      if ( c==0 )
      {
         i--; // No NULL terminators. Try again.
      }
      else
      {
         s[i] = c;
      }
   }
   return s;
}

void hashTest()
{
   srand(123);

   if ( 1 )
   {
      stringToIntMap map;

      {
         int n=0;

         int const testSize = 10000;
         for ( int i=0; i<testSize; i++ )
         {
            int keySize = 1 + (n%10); // Vary key sizes.
            std::string key = randomString( keySize );
            assert( key.size() == keySize );
             n++;

            map[ key ] = i;
         }
      }
      
      // Copy all the keys.
      std::vector<std::string> keys;
      for ( stringToIntMap::iterator it = map.begin(); it!=map.end(); ++it )
      {
         keys.push_back( it->first );
      }

      fprintf( stderr, "!!!! map.size() = %d, keys.size() = %d\n",
               map.size(), keys.size() );

      for ( size_t i=0; i<keys.size(); i++ ) // @@@ numToDelete; i++ )
      {
         assert( map.find( keys[i] )!= map.end() );
         fprintf( stderr, "ERASING %d: \"%s\" size=%d\n", i,
keys[i].c_str(), keys[i].size() );
         map.erase( keys[i] ); // CRASH!!!
      }
      fprintf( stderr, "OK\n" );
   }
}

int main( int argc, char** argv )
{
   hashTest();
   return 0;
}