Thanks to markba's investigations I tried to use freerdp - partly with success:

Use freerdp ( instead of rdesktop. In 11.04 you can just install the package freerdp-x11. Otherwise download the latest tarball and compile it:

Afterwards run it with your desired resolution:
xfreerdp -g 800x600

Also fullscreen is working: xfreerdp -f
(CTRL+ALT+ENTER to leave it again)

It's not excactly what I wanted, but atleast now I can make different launchers for the users to allow them to open the RDP viewer in different sizes. Using the commandline option for VBoxManage wouldn't be an easy option for me because the virtualbox machine is running as a different user. There might be a solution messing around with the sbit or so to allow normal users to run the VBoxManage command as different user, but freerdp was definitly easier and causing less troubles.

Whats not working:
Unfortunatly dynamically resizing the window (as you can do with Windows' RDP-Client) is not working either, it is being discussed already on the developers' maling list:

The packages shipped with Lucid are not working at all. I couldn't manage to get a working RDP connection, don't know why. In 11.04 and by using the compiled tar-balls from the website everything seems fine.