I've used both Google for Domains and Exchange Online. Google for Domains does everything I want - mail, calendars, and access from anywhere. Exchange Online works best for Windows users who are familiar with Outlook and don't want to change.
My current company is using a hybrid system, by accident. We started with Google for Domains, and then added Exchange Online. My primary system is Linux, so none of the Windows tools work for me. The other developers use OS X, which has similar issues. So, I continue to use my Google for Domains account, pulling email out of the Exchange Online account with POP, and sending over SMTP. These are off by default - the admin needs to open a ticket to request these services for each account, and it takes less than an hour. You'll have to do something similar for Blackberrys and other phones.
My biggest issue is that the SMTP interface is sometimes unreliable, possibly due to load, so the mail client needs to be able to retry sending emails. The POP interface may have similar reliability issues. Occasionally, the delay can be hours.
If we didn't already have a Google for Domains account, then I'd link my Exchange Online to my personal GMail account. It is almost perfect - Microsoft for the execs, Google for the developers. If only there was better calendar syncing - I usually have to enter events twice for everyone to see them.