Shell_NotifyIcon(NIM_DELETE, nid)

  Private Sub ChangeTrayIcon(ByVal m_icon As Icon)
    'код вывода иконки в трей
    Dim nid As New NOTIFYICONDATA
    With nid
      .cbSize = IIf(sys_WinVista, Marshal.SizeOf(nid), Marshal.SizeOf(nid) - IntPtr.Size) 'NOTIFYICONDATA_V3_SIZE для XP
      .hWnd = Me.Handle
      .uID = vbNull
      .uFlags = NIF_ICON
      .hIcon = m_icon.Handle
    End With
    Shell_NotifyIcon(NIM_MODIFY, nid) 'меняем/обновляем иконку в трее
  End Sub

    Dim nid As New NOTIFYICONDATA
    With nid
      .cbSize = IIf(sys_WinVista, Marshal.SizeOf(nid), Marshal.SizeOf(nid) - IntPtr.Size) 'NOTIFYICONDATA_V3_SIZE для XP
      .hWnd = Form1.Handle 'Handle to parent window
      .uID = vbNull 'Id of the icon
      .uFlags = NIF_INFO 'Options: show balloon
      Select Case the_message.m_type
       Case MessageType.MES_NEW_VERSION_AVAILABLE
          .dwInfoFlags = IIf(sys_WinVista, NIIF_USER Or NIIF_LARGE_ICON, NIIF_USER)
          .szInfo = the_message.m_error_text & Chr(0) 'Message
          .szInfoTitle = strL_Notify_Title_NewVersion & Chr(0) ' 
          If sys_WinVista Then .hBalloonIcon = IconNotify_NEW_VER.Handle
...
      End Select
    End With
    Shell_NotifyIcon(NIM_MODIFY, nid) 'Show balloon

uTaskbarRestartMsg = RegisterWindowMessage(TEXT("TaskbarCreated"));

if(message == uTaskbarRestartMsg)
{
// Shell_NotifyIcon(заново);
}