snakecatcher,

две цитаты из описания ExitWindowsEx :

This flag can be used only by processes running in an interactive user's logon session.To shut down or restart the system, the calling process must use the AdjustTokenPrivileges function to enable the SE_SHUTDOWN_NAME privilege. For more information, see Running with Special Privileges.
То есть по идее сервису нужно включить опцию "Allow service to interact with desktop" и вызывать AdjustTokenPrivileges перед вызовом ExitWindowsEx.

Если это не поможет, то посмотри пример использования функции WTSLogoffSession из обсуждения Logoff interactive users in Windows from a service на stackoverflow.