With Exchange/ActiveSync and no Blackberry Enterprise Server, here is how I see it break down.
Windows Mobile
Pros: Full support for ActiveSync, Office apps and Office Communicator Mobile (OCS). Full security benefits of ActiveSync. Most likely to have third-party software available for your VPN or similar such things. Large selection of carriers.
Cons: Obviously, Windows Mobile is getting old and crusty compared to the competition. 7 will be out latter this year but software will probably need to be rewritten for managed code. Mobile 7 may end up being great, but its hard to say at this point. Some smaller carriers don't have a good Windows Mobile selection.
iPhone
Pros: Great ActiveSync support and good support for the security features of ActiveSync. Multiple mailbox support coming in OS 4. You certainly can't complain about the iPhone OS and UI. OCS support is available with iDialog, but it is not free.
Cons: Currently locked to AT&T, and honestly, their data coverage sucks if you have a traveling workforce -This may not be an issue by the end of the year. You will probably have to support iTunes on your desktops. Its possible the iPhone may lag behind in new Exchange features since they are not Microsoft.
Android
Pros: Good selection of carriers although some smaller carriers won't have Android phones. UI is quick and the OS is "open".
Cons: Exchange support is currently only supported with NitroDesk TouchDown. The software works but it does not integrate real well with the OS. Additionally, I'm not sure if you are going to find Communicator software, and third-party VPNs probably don't have applications available yet.
BlackBerry
Pros: It's a popular phone that your business users may already be familiar with. It has a good set of "business" apps available as that is the target market of the OS. Good selection of phones and carriers.
Cons: ActiveSync will only work by installing an application called AstraSync. AstraSync works but it is not as good as using BES. There is also an outside chance that RIM won't allow these guys to operate forever because it cuts in to their BES sales.
My recomendation - We use all four phones in our environment where we need ActiveSync support (no BES). I would recommend the iPhone except for the fact that AT&T is basically your only carrier choice. With that in mind right now, I think Windows Mobile 6.5 is the way to go. It's going to give you the best support for Exchange and the most flexibility with carriers and coverage. If possible though, I would get one of the few models that will be upgradeable to 7 when it comes out.
If Apple releases a CDMA version later this year (which is likely) than I would take a much closer look at that especially with the new features in the v4 OS.