Ugh! Active Directory crap!
1. Open Active Directory Users and Computers
2. Right Click on your domain and choose "Find…"
3. On the advanced tab choose the field User > Proxy Addresses
4. Condition is "Starts with"
5. Value is "SMTP:the_beginning_of_the_email_address"
6. Click Add
7. Click Find Now
Too hard. Too abstract. Why do you hate us, Microsoft? Why can't we just search for it and find it by right clicking?
Thanks to Exchangepedia for inspiring this solution.