Ситуация воспроизводится примерно с вероятностью 0.4 далеко не на всех машинах.
Event log показывает следующее:
1. Timeout (30000 milliseconds) waiting for the MyService service to connect.
2. The MyService service failed to start due to the following error: The service did not respond to the start or control request in a timely fashion.
Первая строчка в моем коде — запись евента в Windows Application Log — записи в логе не появляется, что, видимо, означает — причина не тяжелой реализации OnStart.