That is a very challenging task.
Those things are kept decoded and in binary format.
HKEY_CURRENT_USER\Software\Classes\Local Settings\Software\Microsoft\Windows\CurrentVersion\TrayNotify
"PastIconsStream" = stores the icons data
"IconStreams" = stores the program path, caption and tip
So, technically, if they are coded the same way across all computers, and you would know how your program adds and codes itself there, during installation you could dump both values from user's computer, then add your data and write new complex strings (old+yours) back in the registry.
Or you could try something like Autoit script to do it semi-manually (but user will see what is going on).
Or you could force them all to Show icon and notification (Option two
here), but that would not be fair to the end user.
I do not see an easy elegant solution here.