I'm running Debian as host and I fail to get Debian, Ubuntu, and Fedora guests to be fullscreen. Changing video memory didn't help.
- I haven't tried any other distro
- I didn't create WinXP guest myself
There are a few things that need to be in place. You need to have guest additions installed on the guest OS. You have to have "guest display auto-resize" feature enabled (Host+g toggles this), and then you have to actually activate full-screen mode (Host+f toggles this).
Specifically, on the Debian/Ubuntu guest, run the following (as root):