For the monthly fee, you get a high-quality VPS; a DNS manager; responsive support; and the backing of an active D.O. community; and ... that's pretty much it. If you want e-mail, you have to arrange for that yourself. How many e-mail accounts do you think you'll need? Are there any specific features you're looking for, e.g. web access, IMAP, groupware integration, etc.?

Here's one, of a myriad of options: How To Install iRedMail On Ubuntu 12.04 x64.

I personally use an external mail service (Google apps): http://www.google.com/enterprise/apps/business/

It used to be free but it's not anymore. It's still relatively cheap if you don't have a lot of accounts.

Setting up your own mail server isn't a "do it and forget about it" thing, I don't recommend hosting your own mail server unless you know what you're doing.

I, too, am a big fan of Google Apps. A comparable option is Microsoft's Office 365.