You practically answered your own question in the question itself. The best thing to do is create a hidden window that survives as long as you need the tray icon to exist.
You would call Shell_NotifyIcon()
only once with the hWnd
referring to this hidden window, and have this window post the messages to the individual windows that need to receive them.
This also gives you the flexibility of being able to decide to skip sending messages to a particular window, or being able to send a different message to each window, depending on the requirements of your particular application.