Wann ist ein const_cast angebracht?

[unknown]

Folgendes

UM_Wrapper<Key, Value, Hash, Equals>::key_exists(const Key& key) const
{
  const Key* pKey = &key;
  return data.find(pKey) != data.end();
}

sollte doch funktionieren?

Oder eher nicht, wie willst du denn den Pointer finden? Oder ist die find-Methode von dir (überschrieben)?