After much work, research and exchanges with different people, here is the summary of what I found works and what was tried.
Updating Windows 2008R2 servers from WSUS is not a problem if the Remote Desktop Services were never installed. For example, I was able to update 2 servers which I had set up as domain controllers from Windows 2008R2 SP1 fresh install. That required applying about 150 updates. Took a few reboots and everything installed nicely. A few failed but they did not show up after as being needed - so they were superseded by other updates which worked.
A server which had RDS installed is basically doomed. Installing the updates are going to be a pain. Here is the comments from some MVP guy on this. But even in single-user mode, it's a pain.
RDS Servers require special handling for patch installation.
Researching "Patching Terminal Servers" will turn up conversations
from back in the 2005-2007 time frame when this scenario was first
discussed with respect to WSUS v2. In short, you need to drain the
user sessions from the RDS server and place the server into
single-user mode to successfully install those updates.
So the moral of the story - when you plan to set up a RDS server, install Windows but not RDS, do all the Windows updates. Then install RDS and do any further updates required.
And the second moral of the story - keep your RDS servers updated regularly so you don't have to suffer pain months down the road with hundred of updates to manually install.
--- More to it - later ---
Today, my team found something that has been helping - setting the following Registry Key: HKLM\SYSTEM\CurrentControlSet\services\TrustedInstaller\BlockTimeoutIncrement to a higher value (say 36000). This can be done also through group policy using the "Increase Win Update Timeout".
We found this because we found the windows update log stating that the update had timed out and thus it was rolling back.
Setting this let Windows Update finish installing after many hours and the updates installed.
Does not tell us why it's taking so long - that's still not normal. But at least we were able to do the updates.
Even more
Seems like we have it solved! We started getting other errors on our servers and all this lead to finding that the Administrator NTUSER.DAT file was 1.5GB and using a lot of the resources available to load registry files. This was causing regular users to be unable to log on (when the Administrator was logged on, which was... basically always).
Anyway, so I deleted the local profile of the Administrator user, recreated it by logging on. NTUSER.DAT is less than 1MB.
Ok, so we had a thought - could this solve our Windows Updates issues... well, seems like it did. We can now install Windows Updates like on our non-RDP servers.
So looks like because the registry of the Administrator user was bloated, and this is the user we were logged on with when doing Windows Updates (or installing Hot Fixes), the install took too long and timed out.