I remembered there was a useful command "shutdown -i", that allows rebooting networked computers. I opened Powershell on one of the computers that I have unattended access to and typed it... it opened a GUI, I typed both the server name and its FQDN. None of these worked, as I was running shutdown command in the context of a local user - and the computer isn't even domain joined!
So, I had to figure out how to pass the username to the shutdown command... I typed "shutdown /?" and noticed that there was no way to specify the admin credentials. What am I supposed to do? Google to the rescue! Turned out that connecting to the IPC$ share will achieve what I need. If you already have a network share open, you will probably need to close it first, otherwise you'll get an error message with "Multiple connections to a server or shared resource by the same user, using more than one user name, are not allowed. Disconnect all previous connections to the server or shared resource and try again"
If that's the case, you should disconnect the open server shares. Names of the shares don't really matter. Then, you can connect to the IPC$ share. The IPC$ is a hidden share maintained by the Server service. It is used for Inter-Process Communication by using RPC (Remote Procedure Call), allowing the client to send different commands to the server.
So, type
net use \\server\share /delete
net use \\server\IPC$ /User:domain\username
Type the password for the supplied user account, in my case, it was the domain administrator account. After you see the "Command complete successfully", you can type either "Shutdown -i" to bring the GUI or just type the command like this
shutdown /r /t 3 /m server
In this case,
/r restarts the server, /t specifies timeout, /m - server name. There are many other switches for the shutdown command, just look them up.
A few seconds after I've type this command, the server initiated the reboot!
After a minute or so, I was able to ping it again and this time, both the Remote Desktop and Teamviewer worked just fine. This technique can also be used to restart non-domain joined computers, you just need to know the local administrator username and password.