hpair = new pair<hoge, int>(new hoge(), 0);
hmap->insert(hpair);
delete hpair;

でいけました．
(念のため，memset で hpair を上書きした後も hmap を通じてアクセス出来ることも確認しました．)
delete *i はダメみたいです．

あと，もとのコードでは typename つけないと implicit declaration とかい
うエラーが出てました．gcc v3.3.5 です．