So you have a new pc or a new Outlook profile. You login to your mailbox, all your data is there but your auto complete list which Outlook auto generates has gone, what a pain.
This is actually easy to get back and is basically just a file stored in your user profile on your pc.
Browse to :
C:\Documents and Settings\USERNAME\Application Data\Microsoft\Outlook
Look for a file called Outlook.NK2
The name might be different to that but will still have the same extension of .NK2
Copy or rename the file to it matches your Outlook profile name.
Eg, if your profile name is Fred then copy that file to fred.nk2
Make sure it is in the folder listed above and the next time you open Outlook you should have all your autocomplete info back :)