Internetrecherche hat folgenden Hinweis zur Lösung erbracht:

http://support.microsoft.com/kb/319127/en-us

Ursache:
Vermutlich durch Installation der Lexmark Druckersoftware hervorgerufene Verschiebung beim Start der Dienste, die Druckerwarteschlange wird zuerst aufgerufen und wartet ihre 15 min ab bevor der Serverdienst gestartet wird

Workaround wie beschrieben, da der Eintrag DependOnService für den Spooler schon existiert wird lediglich in die zweite Zeile LanmanServer eingetragen.

Damit haben alle Rechner bei uns ihr normales Verhalten beim Einschalten wieder erreicht.