I've never used Win32::, but having metaCPANned this, I am surprised you are not passing $menu as an event or 'on' parameter to the AddNotifyIcon function instead of the main window, although my surprise could mean nothing of course, under the circumstances.
One world, one people
Comment on Re: Win32::GUI won't display an NI menu properly
I was passing $menu_popup in to the main window to link it in as it seemed to make sense there however I tried adding it to the AddNotifyIcon instead but I get the same problem, it's the displaying of the menu that is the issue.
I can track the right-click, the issue seems to be in the TrackPopupMenu call.