Take a look at
http://www.simplymailsolutions.com/
I've been very happy with them. They use Exchange 2007 (and OWA 2007 is brilliant). I also use their Postini spam service (which is fantastic). Support is very good too.
Avoid Fashosts hosted Exchange offering if you can, they have 12 month contracts now and once signed up you'll be locked in (and getting out even when the contract is finished proved tricky), plus support is non-existant...
For the Blackberry, you can use the free BIS that comes with your Blackberry provider and configure Outlook Web Access which will result in the autosync of Inbox and Sent Items. Then use the Blackberry Desktop software to manage contacts and calendar.
If you want everything synched, then you need to look at the BES option SimplyMS provide (and I don't know many others that offer this, although it would mean that you have to make a change with your Blackberry provider and there is a charge from SimplyMS.
Edit: you might want to look at their simple POP3/IMAP service though (NexGen). I have one user on this - using Thunderbird as the email client. I then set up BIS using the IMAP settings and hey presto, Inbox and Sent Items are synched with BB. Make sure you set the email client up with IMAP as well.
Edited by jhurrell (Wed 17-Jun-09 14:10:20)