Found it out.
As described in https://groups.google.com/g/qubes-users/c/RogG5rXG_Pw, you need to ensure, qrexec-client-vm is invoked, when qubes-qrexec-agent.service is still active.
Hence add following to shutdown.service (under [Unit] section):
After=qubes-qrexec-agent.service
Also it needs to be a system - not user - service.