Server 2003 R2 SE (x86) Terminal Server Service failure

So, I'm having an odd and new to me problem on one of our Server 2003 R2, SE x86 VMs.

The long and short of is that ever since patching last month, we can't seem to RDP into the box, and we do need to from time to time, because it's our Exchange (2003) server, and we occasionally have to administer our mail environment. Attempting to connect over RDP throws a 2308 error code. For what it matters, non-RDP remote connections seem to work fine (PSExec, remote Event Viewer, etc.).

Since it's a VM, I popped on to take a look through the vSphere console, and found the TermService Service to be started, but reverted to Manual Startup Type, and in a NOT_STOPPABLE, NOT_PAUSABLE, IGNORES_SHUTDOWN state.

I changed the startup type, did a takskill /PID /F and restarted the service, but it's still not accepting connections, and is back in a NOT_STOPPABLE, NOT_PAUSABLE, IGNORES_SHUTDOWN state (which is not the state it's normally in), and not accepting connections. Terminal Services Manager shows the two "available" RDP sessions as down, and throws an error if you attempt to reset them.

I have seen references online to this being a result of multiple network cards, but our server just has the one vNIC.

As this is our only Exchange server, rebooting it is a last resort (doubly so because of the red tape we inflict on ourselves around doing so for any server), so does anyone know what's going on, and hopefully have a solution that doesn't involve rebooting?

Screenie below, in case anyone needs the visual.

Sorry to say - I've seen some Win2k3 servers end up in this state, and I have never had any luck in restarting the TS service successfully. A reboot is your answer, sorry to say.

For preventing a repeat: The way this has happened IME has been initiating a reboot via the GUI inside an RDP session. I think you'll find that the last time this was patched, a reboot was initiated but didn't complete - check the uptime and event log for confirmation of this. The fix is to fire up CMD.EXE and run shutdown /r with any other appropriate switches, and keep a ping -t exchangeserver from another machine to ensure that it actually goes down. If it doesn't, you'll have to use something OOB to force a reboot.