Somebody on Gamedev.net suggested changing the settings in the "Log on" tab of the service's properties, to use the Local System account, and check the "Allow service to interact with desktop" box. This seems to work for me, it's not an XNA application but my CruiseControl.NET service is launching a commandlet that generates thumbnails using D3D9, and I had the same problem as you initially.
@Bjoern: I guess you would want to use DirectX in a service for the same exact reasons you would want to run any other app :) In the company I work for, we currently have 12 build servers performing various tasks for our game, and mostly I want everything to restart automatically when they reboot (for example, after some Windows update was pushed), without any user having to log in.
Frederic