Create a web portal (LAMP is fine). Authenticate it against AD/LDAP. Allow users to choose an email address. First come, first served. Make useful suggestions based on their name/initials. Implement workflow and approval so that junior help desk staff can approve chosen email addresses based on policy set by you (to avoid firstname.lastname@example.org). Make sure old email addresses remain as aliases foreever as these may be published in academic papers etc. You can keep the portal so that people can update their info and create new aliases when their name changes (getting married/divorced etc). Sorted.
..."Live Free or Die".