Recently used folder logic sounds good !
With the Name Completion though, you are playing with fire for people that are creatures of habit.
The same people that hate MS Office dynamic menus that hide "seldom used" functions such as "Save" will have trouble coping with the names being presented in a different order. At least with alphabetical order they can understand the logic.
A related complaint we have is due to Frequent Contacts being before the System AB by default. Frequent contacts learns the recipient's home email account (which has the same display name set) and presents it first, instead of the "internal" address. The amount of emails sent to Gmail when it was intended to be internal is amazing. Blaming the user for this doesn't stop the problem occurring. Well intentioned helpdesk staff who just delete the Frequent Contact entry (which is quickly relearned) further compound the issue.
Now if only we could administratively set the Name Completion Search order....
Or maybe we can go back to prompting the user when we have multiple identical names - except we can ask to merge the records and set a preferred address ?