> Until 2 days ago, when I started to compose a new e-mail message and
> went to the "To" field, as soon as I started typing a name it would
> give me addresses of people that I often e-mail to, even if they were
> not in my address book.
This is called the autocompletion cache and, as you note, it is unrelated to
your Contacts folder (Outlook has no address book. The "address book" is
just a view of your Contacts folder(s)).
> As of 2 days ago, Outlook gives me some
> options of e-mail addresses, but often not the one I am looking for.
The autocompletion cache can hold at most 1,000 entries. Perhaps you've
reached that limit and the entry you want has been removed. The cache still
seems to be operational if you can still see some entries.
> It used to be that I just had to receive a message from someone, and
> then Outlook would be able to find that person's address again as
> soon as I started typing their name in.
I don't recall any version of Outlook doing that. I do recall that Outlook
2000 in Internet Mail Only mode had the ability to store addresses to which
you replied in Contacts, and current versions also have this ability with
add-in code.
There are a couple of tools that allow you to manipulate your autocompletion
cache. The most complete one is commercial and can be found at
http://www.ingressor.com/ . There is a free tool as well, but it's
abilities are very limited. It can show you, though, the contents of you
cache. See http://www.epute.com/nk2csv/

Signature
Brian Tillman