It's been years since I last saw a graphics card that wasn't properly supported on Linux, and quite a while since I last saw a single-framebuffer card. The two biggest off-board chipsets, nVidia and AMD (ex ATI) both offer well-supported multi-screen configurations for X11 on Linux (closed-source binary drivers may be needed to enable all features on some chipsets).
After a tiny amount of research, I found a sub-£20 card with a well-known chipset and three ports (VGA, HDMI, DVI). You can attach the two digital outputs to two monitors and they'll work fine.
I'd optimise on the feature set of the cards, not the availability of double framebuffers.
Also, if your workstations have on-board video, and depending on your needs, you can get a card with a single framebuffer (assuming you can find them) and get two displays that way — they don't need to be provided by the same card!