I'm sorry I didn't mention it earlier, we use NetQMAIL + VPOPMAIL + mysql centralized auth.
with this kind of setup you should be able to get insane availability figures using standard tricks like ups, quality hardware (no ata), conservative time-proven settings, raid... (i do)
having two cheaper boxes setup with some fancy replication clustering between them will likely to be more trouble than one expensive.
my guess is that your weakest point is mysql. you shouldn't find it too hard to have the auth part replicated, but when it comes to the mail repository, as far as i know maildir storage is *not* the choice for replication.
/k
