I think most hosting companies would provide you help for setting-up a webmail, it's quite easy to do so. If not, they are dumb, and you should leave asap IMHO.
GPLHost:>_ open source hosting worldwide (I'm founder, CEO & official Debian Developer)
Servers & our leading control panel and our Xen VPS hosting, which are already included in Debian and Ubuntu
Available in: Kuala Lumpur, Singapore, Sydney, Seattle, Atlanta, Paris, London, Barcelona, Zurich, Israel