If Key is char*, the assumption that const Key is const char* is wrong. const Key is char* const.
typedef std::map<char*, void*, stlcompare_char, TestAllocatorA<std::pair<char* const, void*> > > MAPTEST;
What is the difference between const int*, const int * const, and int * const?