As far as I know, everyone is doing this manually right now.  I
certainly am.  I want to change this though.

LDAP is something I know nothing about, but might be a good option
especially if you have an existing (corporate?) address book.

Interfaces to an external address book is also a possibility. 

There are some very interesting options to use the message index
information as a fast automatically collected database of "important"
email addresses.  This is done previously by JWZ (?) Big Brother
Database for emacs mail reading.  I do this manually by using the
"Participants Filter" to find the email address of my intended
recipient.  I tried some experiments with this last week but have not
finished it.

Mike