How to change resolution on Vista when it keeps booting to an unsupported resolution?

Instead of safe mode boot to "Low Resolution" mode. It should be a few menu options below Safe Mode in that list.

Alternatively you can open msconfig from a command line. Navigate to the Boot tab, and put a check in the Base Video box from safe mode and reboot.

Edit: To answer your second question about detection. A monitor identifies itself to a computer, along with its specifications and native resolution over something called an EDID. The EDID resides on a ROM chip in the monitor and is a standard.

However OS vendors (such as Microsoft), video card manufacturers, and monitor manufacturers have typically done a mess of a job implementing it. This leads to shoddy support for advertisement of native res, etc, and when this happens, it causes problems like the one you are having.