When typing a name or address in the TO field it will automatically complete the address or name with one stored in history.

To delete this history, go to:
C:\Documents and Settings\username\Application Data\Microsoft\Outlook\

and delete

username.NK2

Outlook will automatically re-create that file, so you will need to delete it each time you want to clear that cache.

...Or you can start typing a few letters into the "TO" field, and the list pops up, notice the first name in the list is highlighted. You can use the up and down arrows on your keyboard to move throught the list, and hit "delete" on a highlighted name to delete that entry from your list.