Ich hab die Ursache nun gefunden.
Im SysLog wurde auch das Event 36885 Quelle Schannel protokolliert. Leider zeitlich getrennt vom Auftreten des Fehlers.
Dieses besagt, dass die Liste der Root-Zertifikate zu lang ist und deshalb abgeschnitten wird.
Server 2008 R2 hat hier eine Grenze von 16384 Byte.
Scheinbar sind dann die Zertifikate die WinRM benutzt abgeschnitten worden weshalb keine Verbindung aufgebaut werden konnte.
Die Auslieferung der Liste komplett unterbunden und schon hat alles wieder funktioniert.
Jetzt muss ich nur noch schauen, welche Root-Zertifikate ich löschen kann.