Google Contacts Autocomplete is a Greasemonkey script that brings your Gmail contacts everywhere you go on the web. When you start to type the name of your friend or his email address, the script shows a list of suggestions.

For now, the script only provides suggestions for a single email address, but I'm sure this could be easily fixed. Unlike Gmail, the script sorts the suggestions alphabetically, not by affinity.