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.