You will want to test for a message sent to top level windows when Explorer restarts.

Code:
Private WM_IECrashNotify As Long
' ^^ add as module level variable

' at sometime before or after assigning the tray icon. 
' If called multiple times, will always return the same value
WM_IECrashNotify = RegisterWindowMessage("TaskbarCreated")

' Now test for that message in a top level window's subclass procedure
Select Case uMsg
   ....
   Case WM_IECrashNotify 
        ' start your icon again.  It was destroyed when Explorer Crashed
   ....
   Case Else
End Select