I had a long and frustrating experience trying to get multi-monitor KVM to work properly. Here's a synopsis of my experiences:
I've ended up using two HP LP2065 monitors that have two DVI inputs and an old Belkin PS/2 KVM switch for the keyboard and mouse. The system still loses track of the keyboard and mouse occasionally. In order to fix this, I plug USB keyboards and mice directly into the Windows computer or ssh into the Linux computer and reboot it. Generally this happens about once every couple of months.
In the beginning I had two Viewsonic VP2030B monitors and a Matrox G450 card. The Matrox cards have good quality DACs and the Viewsonic monitors have a DSP that sharpens VGA signals. Picture quality was quite good and I used a pair of Belkin VGA/PS2 switches to flip between the computers. At one point I had four computers going off one of the monitors and two off the other one.
Later I had the bright spark of trying DVI with the Viewsonics. Unfortunately that monitor had a firmware bug where it would often lose track of the digital signal on the DVI. I bought two (quite expensive) Avocent DVI/USB KVM switches and some fairly expensive cabling. When the monitor lost the plot the KVM switch would assume there was no monitor connected and lose the plot too. Most of the time the Viewsonics would drop back to VGA mode if the process worked at all. Generally the whole lot would crap out every few days requiring about an hour of nitpicking fiddling to get it back up and running. Fail.
Then I replaced the Viewsonics with HP LP2065s, which don't have an edge-sharpening feature for analogue signals. The switches were still quite flaky and would default to analogue signals. Replacing the DVI-I cables with DVI-D only cables fixed the analogue problem but the setup is still quite unreliable. Similar issues persisted with a Startech and Gefen switches and firmware upgrades to all of the switches. Fail.
At that point, with nearly £1000 down the drain, I gave up on DVI KVM switches and have some serious reservations with recommending that people use them.
The current setup using two monitors with multiple inputs and just switching the monitors works fairly well - it loses the plot every few months rather than every few days. All that is needed for this is a single cheap switch like my old Belkin. One point to note is that USB handles keyboards and mice being unplugged and plugged back in much better than PS/2 does - I use a USB keyboard and mouse to rescue Windows machines if the KVM switch loses the plot.