As long as the users are logged on, you could also run a system tray application on the users desktop which interacts with the service.

I think that's also the way officially proposed by Microsoft: Write a privileged background service and use a dedicated application running in the context of an ordinary user for the user interface. Windows offers serveral ways for IPC between the two processes. Named pipes and IP sockets (via localhost) are commonly used.

To start an unprivileged process running under the user account, the service process simply sends a message to the user interface process, containing all required information.

And to start the unprivileged user interface process, use one of the various autostart mechanisms. Creating a shortcut in the Autostart group of the start menu is a very simple way, other ways need some registry editing.

Alexander