//в CMainFrm::OnCreate
m_taskbar.SetNotifyIcon(m_hWnd, MY_WM_TASKBAR_NOTIFY, IDR_MAINFRAME);

//CTaskbar::SetNotifyIcon
BOOL CTaskbar::SetNotifyIcon(HWND hWnd, UINT uCallbackMessage, UINT uResource)
{
ATLASSERT(hWnd != NULL);
ATLASSERT(uCallbackMessage != 0);
ATLASSERT(uResource != 0);

m_nid.cbSize = sizeof(NOTIFYICONDATA);
m_nid.hWnd = hWnd;
m_nid.uID = 0;
m_nid.uFlags = NIF_MESSAGE;
m_nid.uCallbackMessage = uCallbackMessage;

m_nid.hIcon = (HICON) ::LoadImage(_Module.GetResourceInstance(),
MAKEINTRESOURCE(uResource), IMAGE_ICON, 16, 16, LR_DEFAULTCOLOR);
if (m_nid.hIcon)
m_nid.uFlags = m_nid.uFlags | NIF_ICON;

if (::LoadString(_Module.GetResourceInstance(), uResource,
m_nid.szTip, sizeof(m_nid.szTip)/sizeof(m_nid.szTip[0])))
m_nid.uFlags = m_nid.uFlags | NIF_TIP;

BOOL fResult = Shell_NotifyIcon(NIM_ADD, &m_nid);

if (m_nid.hIcon) {
::DestroyIcon(m_nid.hIcon);
m_nid.hIcon = NULL;
}

return fResult;
}

возможно я был не понят — в 99% иконка в трее появляется. иногда не появляется при загрузке 2000/XP если включен autologon
сейчас хочу попробовать сказать NIM_SETVERSION c 0, посмотреть, что получится.