The drop-down list of names that Outlook gives us to auto-complete a name or address being written is stored in a file called <ProfileName>.NK2 in our Application Data\Microsoft\Outlook directory. This file is stored in a proprietary binary format, and there's no known documentation for it as far as I know. There seems to be a company that (apparently) reverse-engineered the format and are selling a cache-editing tool, but it's pricey - the basic desktop version can edit, import/export and print for $35. The network/helpdesk editions can do remote NK2 editing for all computer on the network, but gets really pricy with per-seat licenses and so forth.
(They're called Ingressor, if anyone needs those tools)
It turns out, however, that the most common usage for such an editor isn't necessary. If we just want to remove an item from the cache we can do it from within Outlook itself - simply navigate the drop-down options using the arrow keys and press Del on the one we want to erase - and away it goes.
Very simple, and even logical when you think about it. We're just not used to live editing of an auto-complete list.