If you're able to talk to AD with LDAP utilities, it should be pretty easy given a list of emails. I use a similar command to build a list of every email address we're willing to accept delivery for so it can be pushed out to our Postfix mail gateways. If you worked for the Patriots, and only knew Tom Brady's email address of 'firstname.lastname@example.org', this would get you all of his other addresses (the one with SMTP in caps is the default reply address in Exchange). The ldapsearch command is line-wrapped:
ldapsearch -h corp.patriots.com -x -D email@example.com -w 'AGoodPassword' \
-b 'dc=corp,dc=patriots,dc=com' 'proxyAddresses=smtp:firstname.lastname@example.org' proxyAddresses
# Tom Brady, UserAccounts, Accounts, corp.patriots.com
dn: CN=Tom Brady,OU=Players,OU=Accounts,DC=corp,DC=patriots,DC=com
Most of that command is just the configuration of the ldap connection, allowing it to connect to any domain controller by specifying only the domain name as the host. The -x is to do simple authentication instead of SASL, then I give the UPN and password of an account specifically created as a Domain Guest only and solely for the purpose of running a few different little scripts like this. The -b option is telling it where to start the search, so you can narrow it just to a specific OU or something, though here I just search the entire directory.
After all that, you get to the bits you're actually interested in, first a search filter of 'proxyAddresses=smtp:email@example.com' since you know that email for him, and then the attribute(s) that you want back. Here I only want proxyAddresses, but you could instead ask for telphoneNumber, streetAddress, state, or whatever you have populated in AD (or you can get back everything AD knows about a user by leaving the attribute off altogether... then you can use the output from that full search and pick any of those other attributes to use as your search filter).
Aplogies for the length, didn't mean to ramble but I have no idea how much of that is familiar to you or not.