Outlook Email Address Caching

[kornping]

A strange Outlook query;

The user composes a new e-mail and types in the users e-
mail address in the 'To :' field, when he starts to type
the address a box appears below the cursor with a e-mail
address for that person.

This is because this is an address he has sent to before.
User is doing this now and sending to a user he has e-
mailed before but he has to type the whole e-mail address
in now and doesnt get the e-mail address prompt below the
cursor.

I know that the cache history would be reset if the user
has either a new w/s or a new profile but this is not the
case. Any ideas why this would keep resetting?