On peut supprimer ces adresses au fur et à mesure et cette fonction n'est pas propre à Lion, elle existe depuis quelques versions d'OS X. Lorsque l'une d'entre elles est spontanément affichée par Mail, cliquez sur la petite flèche en regard du nom. Choisissez ensuite l'item "Supprimer de la liste Destinataires précédents".

Si cette commande n'apparaît pas, c'est que le contact en question figure dans Carnet d'adresses. Nul besoin d'ouvrir ce dernier pour supprimer tout de même la fiche, restez dans Mail et sélectionnez Fenêtre > Destinataires précédents.
Là se trouve la liste de tous les contacts avec qui vous avez échangé un courrier, et une indication pour distinguer ceux présents dans Carnet d'adresses. Vous pouvez alors faire un ménage plus rapide par lots, en activant par exemple un classement par date de dernière utilisation de ces adresses.