Best Way to Handle Email for a Small Domain?

CorkBobbingInTheSeaOfLife asks: "Our company just had its bi-annual email crisis/outage, so my boss wants to try something new -- to give me the 'opportunity' to figure out and implement a better way to host our small domain's email. We've changed hosts a few times, but whether we spend a little money or a lot none have been as reliable as we've liked -- companies fold, get blacklisted by AOL, and so forth. Is there a way to be smart about this, without hiring a dedicated email server pro? Do reliable email hosts actually exist? Should we run 'email appliance' software (such as ClarkConnect or E-Smith) on our own server? I'd appreciate any tips here - hell hath no fury like people without email, and I am very afraid..."