This problem is very common for signed .NET service executables: the service will fail to start at boot time, but run fine when started manually afterwards. Whether ServiceBase.RequestAdditionalTime is used is irrelevant: in fact, no user code is executed at all prior to the service start request timing out. This effect is even more pronounced on machines without Internet connectivity: in that case, even manually starting the service from the SCM will fail.
To resolve this issue, disable the verification of the Authenticode signature at load time in order to create Publisher evidence, by adding the following elements to your .exe.config file:
<configuration>
<runtime>
<generatePublisherEvidence enabled="false"/>
</runtime>
</configuration>
Publisher evidence is a little-used Code Access Security (CAS) feature: only if your service relies on the PublisherMembershipCondition will disabling it cause issues. In all other cases, it will make the permanent or intermittent startup failures go away, by no longer requiring the runtime to do expensive certificate checks (including revocation list lookups).
Edit, July 2010: For applications using version 4.0 of the .NET Framework, this workaround is no longer required.