@Nate
Q: "Send AS" is an AD perm and "Full Mailbox Access" an Exchange perm?
That's right. "Send As" permission applies to AD objects and is completely stored in AD. "FMA" is in an Exchange database, and is reflected in the AD interface so you can see it and change it.
Q: How do I grant multiple users "FMA" all at once?
There's no way to to do this through the normal GUI administrative interfaces. It would have to be scripted or done with an additional utility. However, you can grant by inheritance on a test container in Active Directory.
Q: How much AD replication traffic will this generate if I change the ACLS for many users at once?
I'm not an AD replication expert, and someone may correct me or have closer estimates. I believe that the ACL must replicate entirely when you make a change. And there is some network traffic overhead/back and forth with the PDC emulator from making security attribute changes. A lot therefore depends on ACL sizes, which typically depend on number of group memberships. I would guestimate that you're looking at 4K/user/DC if you have less than 80 group memberships on average, and double that for every 100 group memberships above that. Between sites, I would expect you to get a lot of benefit from compression (80%? 90%?).