The Matrox Parhelia has multi-head nicely sewn up with Dual-DVI connectors. I think you can even get triple-head on one card with the DVI -> 2xSVGA dongle.

Comes in AGP, PCIe and even PCI versions, for ultimate cost effectiveness. If you want to really go high res, there are Dual-Link (PCI?) versions for those big displays which require 2 DVI inputs (Apple 30"), and a High-Res one when you need to see 9MP at the same time.

As for Linux support, er, my G400 worked out of the box with Xinerama but with a Parhelia, I have no idea.