I've used Domino on Linux as a replacement Exchange server and its great. Not sure what it costs, but the pilot group of users never even noticed that I'd changed anything! We finally decided to keep the old hardware going (extending the warranty was real cheap), changing from NT to suse, and upgrading to Domino.
Seems a shame that IBM don't market it well, but its a great product. btw... I've also upgraded from Outlook to web access which is a browser based email client that seriously rocks.