No automatic ssh key access on Ubuntu guests

[whatdoesitwant]

My 64bit Ubuntu Karmic and Ubuntu Lucid server boxes (9.10 and 10.04) will not allow ssh key access as long as no user has logged in at the main console. They ask for password authentication instead. Obviously this is an issue when autorunning headless boxes.
(Password authentication is enabled by default in sshd_config. I have had no reason to disable it in these cases because these are local development servers.)

I have heard of this behaviour in Ubuntu with wireless connections. However, my servers are running as either lan + host-only or bridged on my local network with cable mode activated in the VirtualBox settings.

I have switched to Debian Lenny boxes, which do not suffer from the problem. I am still eager to find out what is the matter, though. I assumed that Ubuntu was actually gaining ground on Debian in terms of popularity as a server platform? Was I misinformed?

I started noticing somewhere around virtualbox 3.2.8 and onwards (puel), it may have been going on before then, if not always.
My hosts are Windows 7 64 bit machines. All virtual machines are 64bit server installations. Installed packages for ssh are openssh-server and ssh.