What are the benefits/drawbacks of having a single Exchange Server servicing 5000+ users in multiple locations over WAN links, as opposed to deploying Exchange on existing NT servers in those locations?
The primary issue is the WAN links. If a lot of users need the WAN to get to Exchange and the WAN is down or very slow, then a lot of users will be without an important business tool. What you'll want to do is take a historical perspective of your WAN; count the number of outages you've had, the length of each outage and try to determine the reason for each outage. After gathering this data (and do try to gather it for a lengthy time period of a year or greater if you can), you should have a good picture of how reliable your WAN links are.
Then, you'll want to assess the affected user base (e.g., WAN users). If they are heavy e-mail users whose productivity suffers without e-mail, then your WAN needs to be extremely reliable to make a single Exchange server deployment reasonable in terms of the outage risk and downtime costs. If, however, they use e-mail fairly lightly, or perhaps don't require e-mail to do their jobs, then even with an unreliable WAN, you might just decide to deploy a single server.
Another factor to consider is your administrative model. If you don't have admins in these other locations, then deploying an Exchange server to those locations might mean the additional challenge of remote administration. Most administration can be done with remote control tools like Terminal Services, etc., but those don't work when the server is down, and they can be challenging to use when you need to perform a recovery (that might involve inserting CDs, changing backup tapes, etc.).
Whether you choose one or multiple locations, you should also make sure that your Exchange Server can support the load. You can certainly get 5000+ users on a single box (even 5000 heavy users), but its going to need to be a pretty big box. And that could also complicate things for you, because if you do have a big box, it will also mean big information stores (in the absence of storage limit policies, that is). You may find yourself with public and private stores in excess of 100GB. In some respects, this is OK. Disk space is relatively inexpensive, and both Exchange and Windows have no problem working with stores this large. However, you need to backup (and possibly restore) this data; or you may need to repair a database one day. The larger the database, the longer these procedures take. In fact, you could see your single mailbox store grow so large that you may not be able to back it up in a single day.
There are other things to consider, as well. Of course there is the 'all of your eggs in one basket' concern. If one virus slips in, it could mean disaster for 5000+ people. If half were located on a separate server, it might mean they could be protected or isolated from the infection and only half your users will be without e-mail.
Ultimately, unless you really have compelling reasons against doing so, I think your best bet would be to have multiple Exchange servers rather than a single central server.