Rare error on Tray icon creation, after a user log out / log in

I create a systray icon with:

BOOL TrayMessage(HWND hWnd, DWORD dwMessage)
{
    NOTIFYICONDATA nid;
    nid.cbSize = sizeof(nid);
    nid.hWnd = hWnd;
    nid.uID = 1;
    nid.uFlags = NIF_ICON | NIF_MESSAGE | NIF_TIP;
    nid.hIcon = LoadIcon(hInst, MAKEINTRESOURCE(IDI_MYAPP));
    lstrcpy(nid.szTip, L"MyApp");
    nid.uCallbackMessage = WM_NOTIFYICON;
    return Shell_NotifyIcon(dwMessage, &nid);
}

when the app starts / the window is created:

case WM_CREATE:
    if (!TrayMessage(hWnd, NIM_ADD))
        MessageBox(hMainWnd, L"Tray error.", 0, 0);

This error messagebox:

never happens when I launch the .exe normally.
only happens after a User Logout / User re-login, once every 5 launches on average (my app is automatically launched on every session startup with a TaskSchedular task)

Of course when the error happens, the icon isn't displayed in taskbar.

What could be the reason?

The systray system is not ready yet (very short after a user logout / login again) ?
The taskbar itself is not ready yet?
Should I move the creation to somewhere outside of WM_CREATE?

Edit: after @RbMm's comment, I tried this:

case WM_CREATE:
    TrayMessage(hWnd, NIM_ADD);
    // I removed MessageBox(...) from here
    uTaskbarRestart = RegisterWindowMessage(TEXT("TaskbarCreated"));
    ... 
    break;

default:
    if (message == uTaskbarRestart)
    {
        TrayMessage(hWnd, NIM_ADD);
        MessageBox(hMainWnd, L"TaskbarRestart", 0, 0);
    }

Result of this test: the cases for which the tray icon fails to be displayed are exactly the cases when the MessageBox TaskbarRestart is not shown, i.e. when TaskbarRestart event never comes to the message loop... That's strange...

Note: this only happens after a user logout / re-login.

Solution

The current version of MSDN Shell_NotifyIcon doesn't show it anymore (such a shame!), but fortunately, there's an archived version here that gives two interesting informations:

Returns TRUE if successful, or FALSE otherwise. [...] You can call GetLastError for more specific information about a failure case. The most common cause of failure is that the taskbar window doesn't exist or is unresponsive. GetLastError in that case returns E_FILE_NOT_FOUND.

Handling Shell_NotifyIcon failure
Shell_NotifyIcon will often fail when called during Windows startup (for instance, if your application is listed in HKLM\Software\Microsoft\Windows\CurrentVersion\Run. This appears to be because the system is busy starting applications. The failure is more common on low-spec computers or computers with some brands of antivirus software installed, which seem to be very intensive at startup.

Unfortunately, you cannot rely on the error code returned by GetLastError. When Shell_NotifyIcon returns false, some of the common errors returned by GetLastError are:
ERROR_FILE_NOT_FOUND (2)
ERROR_TIMEOUT (1460)
ERROR_SUCCESS (0)
The most appropriate response to any error returned by Shell_NotifyIcon is to sleep for a period of time and retry.

An explanation of why the error code may differ has been made by Paul Baker, paraphrased from http://groups.google.com/group/microsoft.public.platformsdk.shell/msg/59235b293cbf5dfa and http://groups.google.com/group/microsoft.public.platformsdk.shell/msg/73973287f15c03fc:

Shell_NotifyIcon actually calls SetLastError(0) initially. After that, basically it uses FindWindow to find the tray notification window. If this fails, it will typically return ERROR_FILE_NOT_FOUND. Otherwise it sends a WM_COPYDATA message to the tray notification window, using SendMessageTimeout with a timeout of only 4 seconds. If that message returns zero, then Shell_NotifyIcon will fail with GetLastError returning zero.

Solution:

case WM_CREATE:
    ...
    if (!TrayMessage(hWnd, NIM_ADD)) 
        SetTimer(hWnd, IDT_TIMER1, 4000, (TIMERPROC) NULL);
    break;

case WM_TIMER:
    TrayMessage(hWnd, NIM_ADD);
    KillTimer(IDT_TIMER1);
    break;