A customer reported that even after uninstalling their application, the notification icon entry remains in the Notification Area Icons control panel.
Yup, that's right. Explorer remembers the icon, even after the underlying program has been uninstalled, because you might have uninstalled it with the intention of immediately reinstalling it, so Explorer remembers the icon in case it comes back. But after one week, Explorer gives up and finally forgets about the icon. "It's been a week, and the user hasn't reinstalled the application. I'm going to give up waiting for it."
The customer wanted to know how they could remove their icon immediately upon uninstall. They reported that having the icon remain in the Notification Area Icons control panel made it appear that the uninstall was unsuccessful.
There is no documented mechanism for removing the icon (and the undocumented mechanisms destroy all the icon history, not just the icon history for your icon, so don't do that either). You'll just have to wait seven days for the icon to go away.
(One possibility that was considered was to have the Notification Area Icons control panel check if the application is still installed before showing it on the list. This runs into problems, though, if the application resides on the network or removable media. It means that opening the Notification Area Icons control panel can stall on network I/O, generate security audits if you lost access to the network share, and spin up external media. Remember how much people hated it when Windows 95 spun up your CD-ROM drive the first time you clicked on the address bar?)