I use a KVM on my home machines and I see similar behavior when I start up a linux box while the KVM is pointed to a different machine. If I restart the offending box, it comes up in the expected resolution. I had assumed that when booting, the system probed to find a P&P response and if not found, defaulted to VGA. It only does this when booting without a monitor present, so it's not that much of a pain for me.
So, Greg, was my assumption anywhere close?