Ich würde Dir empfehlen eine extra Anwendung zu schreiben, die sich in den Tray setzt und mit dem Dienst kommuniziert.
Dienste, die direkt mit dem Desktop interagieren sind eine große Sicherheitslücke.
Ansonsten einfach den Dienst als "interaktiv" registrieren und schon sollte es gehen.
Solche Dienst sind wirklich nicht die Freude:
SHATTER ATTACK
...
...