仕方がないので、ルートアイテムを選択し、さらに選択解除状態としておくと、選択解除に成功したっぽい動作になるので、これでなんとか回避した。
HTREEITEM hitem = m_Tree.GetRootItem();
m_Tree.SelectItem(hitem);
m_Tree.SetItemState(hitem, (UINT)~TVIS_SELECTED, TVIS_SELECTED);
HTREEITEM hitem = m_Tree.GetRootItem();
m_Tree.SelectItem(hitem);
m_Tree.SetItemState(hitem, (UINT)~TVIS_SELECTED, TVIS_SELECTED);