exchange is generally a better option, although the open version of the same thing (which predates it) is called IMAP.
in terms of who you should use... i'm with fasthosts and have been for ages, and it's also who my current employer uses. i've previously been with 123-reg as well, but find the fasthosts email the better of the two, and it's exchange-based rather than pop3. you can add extra email addresses to the domain, too, for additional cost.
however, they're all much of a muchness, really. i'd just get a recommendation from whomever it is that does your website in terms of hosting, and use that host for your email as well.