I didn't know how to get Evolution's auto-complete feature to behave, so I Googled around. The most useful HOWTO was here:
http://www.sigmundvoid.com/2007/07/evolution-mail-client-and-auto-comple...

But it's down for now. Google still has a cache of the page, so I thought I'd take it while I still can. It's too useful to die!

Evolution mail client and auto complete addresses.

Evolution is a wonderful mail client based around Gnome, you can think of it as the Outlook alternative for Linux users, it can even connect to Microsoft Exchange server.