The ability of applications to block a pending system shutdown was severely restricted in Windows Vista. The details are summarized in two handy articles on MSDN: Shutdown Changes for Windows Vista and Application Shutdown Changes in Windows Vista.
As that page indicates, you shouldn’t rely on the ability to block shutdown for any longer than 5 seconds. If you wish to attempt to block a pending shutdown event, your application should use the new ShutdownBlockReasonCreate function, which allows you to register a string that explains to the user the reason why you think the shutdown should be blocked. The user reserves the ability to heed your advice and cancel the shutdown, or throw caution to the wind and cancel anyway.
As soon as your application finishes doing whatever it is that should not be interrupted by a shutdown, you should call the corresponding ShutdownBlockReasonDestroy function, which frees the reason string and indicates that the system can now be shut down.
Also remember that Windows Services now run in an isolated session and are prohibited from interacting with the user. My answer here also provides more details, as well as a pretty diagram.
Basically, this is impossible. Windows is going to fight you tooth and nail over starting up a separate process from your Service, as well as any attempt you make to block a pending shutdown. Ultimately, the user has the power to override anything you try to pull. This sounds like something you should solve using security policies, rather than an application—ask questions about that on Server Fault.