Is it possible (and how) to set up two servers to handle mail for a domain (or two domains) in such a way that any of the servers can get down for a while (like few days) transparently, i.e. so that users will still be able to modify own mail over IMAP (like marking it as read, deleting, etc.)?
Getting the mail delivered in any way is easily done by setting MX records; but what mail storage can be used that way? In the best case it should be able to change data at both disconnected nodes and merge (with any way of conflict resolving) on synchronizations (couchdb comes to mind, although not completely applicable here).
I have exim4+courier-imap currently set up, but it won't be a critical problem to replace then with something.
Unless you're having performance/capacity issues, stick with a single active server. In that case, you can rdiff/rsync the mail store and spools between the main machine and a hot standby, then fail over through heartbeat monitoring or a similarly automated script.
If you do run into performance issues, the first thing to do is split off the MTA to a separate machine, where it can keep its queues in RAM without affecting mailbox access. Disk capacity can always be upgraded for the mail store itself. Performance of IMAP services are generally bottlenecked at the I/O level, anyway.
If it's not a problem to replace them with "something," then Exchange 2010 comes to mind. It's fairly straightforward to set up redundancy in both the transport and storage systems.