I can suggest one more approach (not perfect, but worth considering, I think).
Having found the tray window you can send WM_MOUSEMOVE to it with different coordinates trying to guess the icon location. As soon the message is forwarded to your application (wrapped in the message specified when calling Shell_NotifyIcon) you have found it.
if the taskbar is hided the arrow of the balloontip appears outside screen, and it should call the taskbar up, like any normal infotips displayed in the taskbar (eg. see how the XP SP2 security warning does). This ballon instead points to the outside of the screen and it's not painted entirely.
Does anyone know if there is an official mechanism (or have unofficial ideas;)) to keep a tray icon active so that Windows XP does not "hide" the inactive icon? I assume that by updating the icon periodically, I can keep it "active", but that seems inefficient.