HTREEITEMが管理されたハンドルで有れば、実際に使われている物かの判断は
出来るはずなので、こういうことがしたいのであればちゃんと管理するしか無いと
私は思います。実際に実在チェックを現実的なスピードで行なえるように
管理の方法も考える必要があるでしょう。
単なるポインタだけでこれをやろうとするから無理があるのではないでしょうか。
HTREEITEMの話にしてもきちんと解析した結果、そういう実装になっているという
話では無いのでこれを例にしてもあまり意味がないように感じます。

> HTREEITEM hItemParent = m_tree.InsertItem(_T(Parent));
> HTREEITEM hItemChild = m_tree.InsertItem(_T(Child), hItemParent);
> m_tree.DeleteItem(hItemParent);
> m_tree.SetItemText(hItemParent, _T(SetItemText));
> m_tree.SetItemText(hItemChild, _T(SetItemText));
>
> のSetItemText()で親も子もちゃんとFALSEが返ってきます。
> ハンドルにはInsertItem()の戻り値が入ったままです(すでにゴミ)。
これはm_treeのメンバー変数に有効なアイテムハンドルのリストが格納されていて、
渡されたアイテムハンドルがそのリストに存在しているかだけを判定しているのでは
ないでしょうか？
だいたい、aetosさんも言っているけどHTREEITEM はハンドルであってポインタでは
無いのだから。この辺りを混同しているのではないかしら。

> 常識的にはこのような場合、
> 削除されたアイテムや存在しないアイテムを指定されたときは
> わざわざ丁寧にFALSEを返してやらなくてもいいものでしょうか？
場合によるでしょう。
不特定の人が使用するライブラリの場合、身を守るために引数のチェックを厳密に
行なうこともあるだろうし、逆に効率を優先する場合だってあるだろうし。

> わざわざ丁寧にFALSEを返してやらなくてもいいものでしょうか？
この辺は C/C++ 言語規格書でいうところの「未定義の動作」になる話で、
未定義＝誤ったプログラム断片に対する動作であって、何が起こるか不明なもの
・暴走してもいい (Release 版はたいていこういう動作をする)
・エラーを検出してプログラムが強制終了させられてもいい
・正しくエラーを検出してもいい(たいてい既に手遅れだったりするが)
・鼻から悪魔が出てもいい
というやつだ。
デバッグ版ではデバッグの助けになるよう３番目の動作をしてくれれば理想だが
そのために処理が遅くなって、メモリ消費量も増大して、所定の性能が出ない。
リリース版は、十分にデバッグがなされている前提でこういうチェックを行わない。
そのぶん速く、メモリ消費量も少なく、想定される性能が出る、ということ。

俺なら、リリースまでには十分にデバッグされている前提で
リリース版ではわざわざ FALSE を返してやるほど親切なことはしない。
デバッグ版ではどうするかな？
チェックを入れてやるかもしれないし入れないかもしれない。
一緒に開発する周りのレベル次第で判断するだろう。

もし、エラーチェックを入れるとしたら、の話をするなら：

CTreeCtrl の中身は MFC ソース見ればわかるとおり、実のところ
SendMessage の wrapper にすぎないわけで、実処理がどうなっているかは
公開されていないわけだけど

とりあえず Win32 限定でよければやはり MFC ソースにいろいろヒントがあり
AfxIsValidAddress とか AfxIsMemoryBlock とか、その辺で
*不完全ながらも* 調べることができる。
# デバッグ版のみだけどな
# リリース版に入れる必要はないわけで、当然の措置だが
いろいろ入れておけば、少しはデバッグの助けになるかもしれない。
リリース時には除去しておくことを推奨する。

っていうか、デバッグ目的であるなら

渡されたデータにプログラム論理上の明確な誤りがあるとわかった時点で
バグなんだからその場でエラーログを出力して即死すべき、だろう。

渡されたデータに操作員のミスによる誤りがあるなら、エラーで継続すべきだけど。
これはバグぢゃないわけで。

delete 済みポインタとか明らかにオブジェクトをささないポインタとかを渡す
ってのは前者であって ASSERT 類で即死すべきバグ。
その場はなんとなく継続して動くほうがよっぽど有害だと思う。

その意味で
> わざわざ丁寧にFALSEを返してやらなくてもいいものでしょうか？
バグに対しては即エラー検出、終了のほうが有意義。

みなさん解説ありがとうございます。

ポインタ自体の値からは存在自体を判断できないとわかりましたので、
「最近使われたファイル」のように
追加やアクセスをされたポインタを特定数だけキャッシュしてみたり、
全ポインタを1次元配列で別に持たせてみたりという処理を試してみます。

それでもあまり効果が見られない場合には、
存在チェック関数自体を外に出して、チェック自体は利用側の判断に任せ、
実際の操作関数内ではノーチェックでやってしまおうかと思います。