あ，たしかにいろいろ変になってますね．要点だけ切り出そうとして，意味不明になってました．
本当はこんな感じです．（まだおかしなところがあるかも）

fbpair = new pair<foo , bar>(new foo(), new bar());
fbmap->insert(*fbpair);
delete fbpair;

> いったいなぜpairをnewで生成する必要がある？根本的に間違っている。
ある関数から，pair<foo , bar> * を返して，それを map に格納してるからそういう構成にしてます．
pair<foo , bar> だと NULL が返せないので，いまのところ，ポインタを使ってます．また，

pair<foo , bar> hbpair(new foo(), new bar());
return &hbpair;

とかだと，return した直後に hbpair がなくなるのでダメですよね？NULL 使
わずに例外を使え，ていう話もあるかもしれませんが，NULL を返すのはそれほ
ど例外的な状況ではないので出来れば避けたいです．

> 何もかもnewしようとしているところを見ると、もしかして君は普段
> AVAをやってるんじゃないか？ソースをさらした方が何をしたい
> のかも分かるし、それに対してC++ではどういう風にソースを書く
> のかも示される可能性が高いぞ。

はい，その通りです．構文としては理解できても，new しないオブジェクトと
いうのがどうにも自分のなかで整理できてくて困ってます．