I had a weird situation where I was taking an autocomplete database from Outlook 2003 to Outlook 2010 where the account was on Google Apps.
When you set up a Google Apps account, it pulls down an autocomplete database from the Google Apps account (presumably the autocomplete that exists from when you use webmail). But if you were primarily using Outlook (2003 in this case), there is a much larger autocomplete database that you need to add.
You're supposed to be able follow the methods listed here, but they weren't working for me using the NK2 file I had and trying to bring them into Outlook 2010:
What I ended up doing was creating a POP account that allowed me to to import the NK2 file (in my case, I put the NK2 file in the appropriate location \appdata\roaming\microsoft\outlook and created an Outlook profile with a POP account with the same name and it imported automatically). With that, I had NK2 file in the autocomplete stream file.
I tried several times to rename the existing autocomplete stream file with the stream file with no success. The file would revert back to an 1 KB file with no autocomplete data. I can't explain, but I just kept trying and eventually, one time of renaming the stream file with the data I wanted with the name that was associated with Outlook worked. I can't explain what I did differently, but I just kept trying (with the ocassional reboot) and it worked.