Is there a way to set a different value for service startup timeout per service? I can change it using the ServicesPipeTimeout registry key, but it's per machine (http://support.microsoft.com/kb/824344).
At the moment the only thing I thought about was to do all the time-consuming startup actions in a different thread.
It's good practice to finish starting your service as fast as possible. So, during the start state, do only what you absolutely need to acknowledge it started successfully; and do the rest later. If the start is still a lengthy process, use SetServiceStatus periodically to inform the Service Control Manager that you have not yet finished, so it does not time-out your service.