Как часто бывает, сам спрашивал — сам отвечаю.
Нашел способ. С помощью SetConsoleCtrlHandler можно получать уведомление о shutdown через handler-функцию, причем оно приходит раньше SERVICE_CONTROL_SHUTDOWN. Мало того, пока из handler-функции не вернуться, службы не начнут завершаться, т.е. эти вызовы синхронизированы.
В общем, таким образом сохранение при shutdown проходит успешно, что собственно и требовалось.