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.
I agree with Romulo on finishing to start your service as soon as possible. However, if you need the time and you are using .NET Framework 2.0 or later, you might consider ServiceBase.RequestAdditionalTime() method.
http://msdn.microsoft.com/en-us/library/system.serviceprocess.servicebase.requestadditionaltime.aspx
protected override void OnStart()
{
this.RequestAdditionalTime(10000);
// do your stuff
}