We are doing the same thing for over 2500 users. We are implementing <b>Exchange 2007</b> with three main entry points and local mailbox/CAS servers at each site. WAN bandwidth is expensive so we did not plan on having any centralized services. Users have been used to having a local mailbox server in their old GW/Exchange environment. We have had direct support from Microsoft for this project. I recommend that you investigate what services they may have to offer your organization.
The project will go well if you PLAN – PLAN – TEST – TEST – IMPLEMENT -TEST – TEST – MONITOR. The more PLANNING you put up front… the more effective the implementation will be. Testing is another critical part of your project.