Ok, first of all create variable m_TaskbarCreated and assign to it return value from RegisterWindowMessage
This is Delphi example.
m_TaskbarCreated := RegisterWindowMessage( 'TaskbarCreated');
Now in WndProc you will receive a message with Msg parameter equal m_TaskbarCreated when Explorer starts. So you can recreate your Tray Icon.