Yet another report, but I can reproduce it and have some interesting observations.

HP Compaq nx6325 running Kubuntu Hardy (8.04) running KDE3
uname -a: 
Linux 2.6.24-18-generic #1 SMP Wed May 28 19:28:38 UTC 2008 x86_64 GNU/Linux
VMware Server 1.0.6 build-91891
xserver-xorg 1:7.3+10ubuntu10
xserver-xorg-core 2:1.4.1~git20080131-1ub
(by the way, you can get the above from the command "dpkg -l")
graphics card: ATI Radeon
driver: ati

Interestingly I also had the issue on this machine running Dapper and VMware server a year ago, which I guess rules out xserver 7.3. It disappeared when I stopped using VMWare. At that time I though it was triggered by excessive memory usage, as I only had 1GB  but now I have 3GB and only using just over 2.
I believe my old setup was VMware-server-1.0.5-80187 and Kubuntu Dapper (6.06?) i386 (not AMD64). The old setup compiled perfectly, both vmware host and tools.
On my current setup I had to apply vmware-any-any-update117 to get the VMware host to compile, and open-vm-tools-2008.04.14-87182 to get the VMware tools to compile. I had the issue both before and after I got VMware tools properly installed.

I also have the annoying keyboard auto-repeat issue (while typing in the VM, sometimes (or, quite often actually) your keystrokes will be repeated).

steps to reproduce:
NOTE: I have put a lot of time into reproducing exactly the steps needed. The following is the bare minimum of what I need to do to reproduce it. Anything else is irrelevant (in my case). For example, it works fine if I switch to full screen without first clicking inside the VM.
- have a vm running
- switch to vmware
- move the mouse into and click inside the vm
- press ctrl-alt-enter to make it full screen
- press ctrl-alt to revert back to windowed mode
now the problem is there:
ctrl and caps/num/scroll lock does not work
the alt key, including alt-tab works, but when pressing alt-tab it does not release the alt key, meaning i have to press any other key, or tab without alt, to actually switch to another program. It's like I am till holding the alt key.
I do *not* however have the unstability issue. I can continue running anything I want, so it's easy for me to test various proposed solutions.
Note: I can *not* reproduce it by holding the ctrl key while moving the mouse from the guest to the host

both of these methods can be used as workaround, reverting the effect of the issue:
- running setxkbmap
- running System Settings - Regional & Language - then selecting Enable keyboard layouts and applying the changes (or if it's already enabled, disable it - apply - then enable and apply)

Interesting things from /etc/X11/xorg.conf
Section "InputDevice"
        Identifier      "Generic Keyboard"
        Driver          "kbd"
        Option          "XkbRules"      "xorg"
        Option          "XkbModel"      "pc105"
        Option          "XkbLayout"     "gb"
EndSection
Section "Device"
        Identifier      "Configured Video Device"
EndSection

When it's working fine, I get this output from xmodmap:
xmodmap:  up to 2 keys per modifier, (keycodes in parentheses):

shift       Shift_L (0x32),  Shift_R (0x3e)
lock        Caps_Lock (0x42)
control     Control_L (0x25),  Control_R (0x6d)
mod1        Alt_L (0x40),  Meta_L (0x9c)
mod2        Num_Lock (0x4d)
mod3
mod4        Super_L (0x7f),  Hyper_L (0x80)
mod5        Mode_switch (0x5d),  ISO_Level3_Shift (0x7c)

When it's buggy, I get this output:
xmodmap:  up to 1 keys per modifier, (keycodes in parentheses):

shift
lock
control
mod1
mod2
mod3
mod4
mod5

As I can easily reproduce it, anyone with ideas are encouraged to suggest them, and I will try it to see it if will solve the issue.