Isso é estranho, funciona bem para mim aqui (Windows 7 Ult. 32 bits).
Ctrl + Alt + Pausa também deve alternar o cliente RDP para dentro e fora da tela inteira. Isso funciona para você?
Também é possível que o lado do servidor tenha um conjunto de resolução máximo permitido. Embora eu esperasse que isso não permitisse a tela inteira em primeiro lugar, pode valer a pena investigar.
Talvez teste com outro servidor RDP, se disponível?