Оказывается, виндовый сервис перезапустить сам себя не может. Он может себя остановить, но без посторонней помощи запуститься уже не сможет. Начал копать и искать обходные пути. Докопался до динамической компиляции кода в память при помощи CSharpCodeProvider и исполнения этого кода из памяти. Только вот код исполняется из того же процесса (на сколько я понял), что не есть хорошо, так как ни чем мне в этом случае не помогает. Начал копать дальше и искать аналог *nix-ового fork(). Докопался до CreateProcess() и тут ко мне пришло озарение. Написал отдельный исполняемый файл в несколько строчек, в котором инициализирую контроллер сервиса, потом его останавливаю, жду остановки и запускаю. Из самого же сервиса запускаю исполняемый файл отдельным процессом при помощи класса Process. Всё работает замечательно.