The autocomplete cache is stored in a *.nk2 file at C:\Documents and Settings\username\Application Data\Microsoft\Outlook. You can delete the file to start fresh or use the arrow keys (as you are typing addresses in the fields) to select an address and use the Delete key to remove it.
Source
I wonder how it would work if you export the *.nk2 file to your new computer.
If you do a Google search for "outlook nickname cache" or "outlook automatic completion cache", it only talks about removing the file. Maybe some more clicking on Google will find an answer?