Umm, Outlook Express? Is it an example of what you do or don't want?

I can tell you that Thunderbird is both free and has email address autocompletion. That is, I can type in part of an email address and it will suggest matches interactively.