After the other replies to my Q, I continued the path of blaming McAfee :). So I got help from the antivirus-admin of my organization, and was able to solve the issue:
First we tried disabling McAfee Endpoint Security, but it made no difference, so then we completely uninstalled it. And then Sandbox worked fine again.
But also: after re-installing McAfee Endpoint Security again, Windows Sandbox STILL worked.
So my best guess is that something wasn't quite right with McAfee which got fixed after the uninstall and reinstallation.