I was suprised at how many of our users do not use Contacts in names.nsf but rely on Recent Contacts to find email addresses. (I imagine this is the same in many organisations). Our users have been told the disadvantages, but I am sure they wont comply, so they will eventually blame Notes when they cant find addresses!
How about an action button on the mail template for Add To Contacts (the action is under a menu at present)?
Better still would be if the Notes client could check through its synchronised contacts and ask "This correspondent is not in your Contacts, Would you like to add this address?"