Proper way to handle Windows Service Tray App / NotifyIcon startup

Question

For the record, I want to point out two things:

1. I know how to create a Windows Service, I know how to create Tray applications and how to communicate with my Windows Service

2. I have read countless articles on this subject, almost all of them suggest hacks, putting applications in the Startup menu, (old) interactive desktop services, startup scripts etc. I also found very resources for the subject dated after 2010 (aka light years in the world of technology)

What I'm looking for is the proper way to make sure that when my service is installed, every user gets a nice icon in his tray whenever he/she logs on to his/her computer. This is slightly more complex than it seems, and most of the hackish solutions won't work anyway (not that I'd want to use them anyway).

What I want to achieve is twofold. I want to know how to:

1. Start the Tray application WITHOUT modifying any user settings. This means not adding anything to the user startup, not modifying the registry, no startup-scripts or whatever. My company doesn't have fixed seats in almost all of its departments. Any user can log on to nearly every workstation at every time. Ideally the Tray application would be launched from the service detecting a user logging on or the shell being started, and then spawning an instance of the tray application for that user.

2. I'm also looking for a way to handle the startup of the service. For example, when I start up the service and multiple users are logged on to a single machine (which is entirely possible), the service should spawn a tray application instance for each of the users with an interactive logon. This is especially important should the service need to recover. The same goes for when the service is stopped or restarted.

Just to give you an idea, the application I'm writing consists out of a Windows Service, a Tray application that gives feedback to users via notifications and allows them to start op a configuration program that also contains additional information for them, and finally said configuration program that communicates with the service via named pipes. It's all very simple.