The Microsoft Documentation reads:
Notification icons specified with a GUID are protected against spoofing by validating that only a single application registers them. This registration is performed the first time you call Shell_NotifyIcon(NIM_ADD, ...) and the full path name of the calling application is stored. If you later move your binary file to a different location, the system will not allow the icon to be added again. Please see Shell_NotifyIcon for more information.
Since the documentation on Shell_NotificyIcon is rather sparse on how to unregister the GUID again, the following question arises: How do I properly remove the NotificationIcon again when I uninstall the corresponding app again?
There is the brute force approach which is described here, which deletes all system icons and the process explorer.exe must be restarted again. However I'm wondering if there exists more punctual approach.
Another option would be to just create a new GUID, every time a user installs the application or moves it to a new location. Is this considered best practice?
10 year old answer from a Microsoft employee speaks of a possible workaround when changing the path and at the same time claims there is no way to unregister:
There is no way provided to unregister that. If your binaries are Authenticode signed then the registration can move with the application. See the Troubleshooting section in the NOTIFYICONDATA documentation.
Note The only exception to a moved file occurs when both the original and moved binary files are Authenticode-signed by the same company. In that case, settings are preserved through the move.
Both binaries would need to be present simultaneously when the icon is created for the path to be updated.
I personally never use a GUID, I just use the classic ID mode from Win95.