I am also having this problem and unfortunately do not have time to debug it further at the moment.
I had to shutdown the service and then manually kill the java.exe process before restarting the service to get Jenkins to start.
In case it helps:
I'm running 1.606 on Windows Server 2008 R2
I have several slaves running via SSH (I noticed their respective java.exe processs were still running after /safeRestart)
I have many (at least 70) different plugins activated, which may also be related to the problem if this is not occuring within a core only environment.

I'm seeing this issue with the latest version of Jenkins (1.655); seeing the same log messages as Kevin has list above.

I believe it worked correctly when running the service as it was initially installed under the local system account, but changing the service to run under a specified user account (needed for publishing builds to Azure) has stopped the auto-restart working.

For the most part, restarting the service manually on the build server works, although I do occasionally need to kill the Java process as it's holding open the ports Jenkins is trying to bind to.

For info:

• Running a single instance; no slaves
• Running v1.655 on Windows Server 2008 R2
• There are ~25 non-stock plugins installed

I believie I'm experiencing the same issue.
Jenkins running as windows service under specified user account.
Restart via CLI does not work either.
In the jenkins.err.log I can see following info:

WARNING: Failed to restart Jenkins
java.io.IOException: Cannot run program "D:\Jenkins\jenkins.exe" (in directory "D:\Jenkins"): CreateProcess error=87, The parameter is incorrect
	at java.lang.ProcessBuilder.start(Unknown Source)
	at hudson.Proc$LocalProc.<init>(Proc.java:243)
	at hudson.Proc$LocalProc.<init>(Proc.java:212)
	at hudson.Launcher$LocalLauncher.launch(Launcher.java:815)
	at hudson.Launcher$ProcStarter.start(Launcher.java:381)
	at hudson.Launcher$ProcStarter.join(Launcher.java:388)
	at hudson.lifecycle.WindowsServiceLifecycle.restart(WindowsServiceLifecycle.java:136)
	at jenkins.model.Jenkins$26.run(Jenkins.java:4051)
Caused by: java.io.IOException: CreateProcess error=87, The parameter is incorrect
	at java.lang.ProcessImpl.create(Native Method)
	at java.lang.ProcessImpl.<init>(Unknown Source)
	at java.lang.ProcessImpl.start(Unknown Source)
	... 8 more

The system is Windows 2008 server R2, Jenkins 2.19.3

SOLVED: On Jenkins Jenkins 2.249.3 running on Windows Server 2019, I had the same issue and fixed it by adding this access right to the jenkins install dir: "Everyone: read & execute"

It turned out not to work always. We then saw the issue https://issues.jenkins.io/browse/JENKINS-50219

And the fix worked. "safeRestart" now works again.

Thanks to Tom Manning for this:

The fix is to enable the group policy setting "Local Computer Policy->Administrative Templates->System->User Profiles->Do not forcefully unload the users registry at user logoff".

It is an issue with rights which can be fixed in the registry