Если вы используете MSMQ в качестве хранилища подписки, сделайте очередь подписки транзакционной.
Тогда сообщения подписки от службы обработчика событий останутся в очереди подписки рабочей службы даже после перезапуска.
Что касается порядка запуска, служба обработчика событий помещает подписку во входную очередь рабочей службы, независимо от того, запущены рабочие службы или нет.Таким образом, порядок запуска также не важен.
ОБНОВЛЕНИЕ
На самом деле это строго не соответствует действительности, поскольку создание транзакционных очередей обеспечит вам долговечность при перезапусках сервера.
Вы все равно должны получить то же поведение, которое я описал выше, с нетранзакционными очередями.