It seems that whenever I click the Window Restore icon on a fullscreen Remote Desktop instance, a subsequent Window Maximize does not bring me back to the fullscreen. Instead I'm back in crappy maximized-with-vertical-scrollbars land.
The solution?
CTRL-ALT-BREAK
This will toggle you between fullscreen and crappy mode.