Update:
Disregard my past post, I figured out how to use NK2 Edit to work for me to FIX THE PROBLEM! Here's a detailed rundown of how I did it:
The "official" suggested fix from Microsoft (see #3 in Failed Attempts) didn't work for me, but after more research I found a way to solve the problem. It's a lot of work, and it drives me nuts that I have to spend about two days to research and fix a problem that shouldn't exist in the first place, but I've spend a lot of time typing up a description of what I did. Hopefully this will be of use to other people who are having trouble!
The first section of this post covers the things I tried to fix the problem that didn't work. The second (middle) section covers a detailed process to follow that did work (for me). The final section includes some additional tips. I'm running Windows 7 Pro, 32bit, Outlook 2010.
===================================
SECTION 1 - FAILED ATTEMPTS
===================================
After two days worth of research regarding Outlook clearing its auto-complete cache at shutdown, here's what I've learned in a nutshell:
1. The problem file appears to be in C:\Users\USERFOLDER\AppData\Local\Microsoft\Outlook\RoamCache, and they're called Stream_Autocomplete###.dat. I would assume that at any time there should only be one of these stream_AC files, but at times I've seen two of them. Not sure why.
2. Multiple suggestions I've read include running a scanpst.exe file, which is located in C:\Program Files\Microsoft Office\Office14. The tool asks for a file to scan (to try to fix) - and I didn't know what file to select. I tried selecting the stream_autocomplete file, but the tool didn't know what to do with that type of file.
3. Another suggestion involved renaming the RoamCache folder. I tried this, and it didn't work. I renamed it to RoamCache2, and when I started Outlook back up it automatically just created a new RoamCache folder. This did not fix the problem, all it did was leave me with two RoamCache folders.
4. Another suggestion involved downloading MicrosoftFixit50584.MSI directly from Microsoft (do a Google search for it if you want to find the file). This is one of those "Automatic Fix It" programs. It's designed to take an NK2 file from a pre-2010 version of Outlook, and importa that file into Outlook 2010 for you. However, this tool on its own did nothing for me because I never had an NK2 file to begin with. Also, you'll see farther down that this tool shouldn't be necessary anyway since NK2 Edit software can convert NK2 files into DAT files for you.
5. The most common fix I found for this problem was to simply create a new message, then add ALL contacts in the To: (or CC/BCC) fields of the email. Then you can save the email as a draft, and when you open a new message your auto-complete list is back. This did work, but only temporarily. As soon as I would shutdown and restart Outlook, the auto-complete list was completely gone again.
===================================
SECTION 2 - SUCCESS
===================================
The suggestion that DID work for me involved downloading software called NK2 EDIT. I believe Outlook versions prior to 2010 used a data file with the NK2 extension to store auto-complete cache info. OL 2010 does not use this type of file, it uses the Stream_Autocomplete###.dat file instead. NK2 EDIT software (free) works with BOTH TYPES of files and can easily convert either type to the other.
Before attempting to fix the problem, I first made sure my contacts were updated - this is important if you want to have a good list of auto-complete contacts. IT IS IMPORTANT TO NOTE that the auto-complete contacts that appear when typing in addresses ARE NOT POPULATED AUTOMATICALLY BY OUTLOOK FROM YOUR CONTACTS/ADDRESS BOOK(S). Outlook is supposed to automatically create auto-complete addressed based on who you send emails to - not simply by whether or not they exist in your addressbook. Here is a run down of how I fixed the problem using NK2 Edit:
1. Open the address book for Outlook and organize and cleanup all contacts in all address books. Make sure that anyone you want to appear in the auto-complete is IN THE ADDRESS BOOK.
2. Close Outlook and open NK2 Edit. Open/Start a NEW NK2 file.
3. Go to Action > Add Records from Address Book
4. Select all of the contacts that you want to appear in the auto-complete list. This shouldn't necessarily be all of your contacts! (For example, if you have five contacts named John, but four of them you haven't emailed in a few years and the other one you email every day -- you should probably only add the one that you email every day. Otherwise, every time you start to type his name in the To: field, you'll have to select the right John out of a list of five.)
5. Once the list is complete, SAVE the list as an NK2 file with a name that makes sense for future reference, such as "Outlook 2010 Auto-Complete Cache File, created in NK2Edit, 2011.11.17". This file will serve as a backup in case the cache file ever becomes corrupted again.
6. Now for getting this file to play nicely with Outlook! First make sure Outlook is NOT running. Then, go to: File > Save As. Browse to the C:\Users\USERNAME\AppData\Local\Microsoft\Outlook\RoamCache folder and OVERWRITE the existing Stream_Autocomplete###.DAT file. To do this you'll have to use the drop-down box under the file name box to change the file type from NK2 to DAT.
7. Close NK2 Edit, and open Outlook. Verify that the auto-complete list now matches the list you created in NK2 Edit by typing a few email address into a new email message.
===================================
SECTION 3 - FUTURE TIPS
===================================
Going forward, a few tips:
1. As you make changes to the auto-complete list, remember to save updated copies of the NK2 (or DAT) file that you update using NK2Edit (see step #5 above in Section 2).
2. In Outlook, once an auto-complete name pops up, it has a black X to the right of it. Clicking the X will remove that name from the auto-complete cache, but not from your contacts. However, the only way I'm aware of to add it BACK to the auto-complete list is to manually add it back to the NK2 file using the NK2Edit software.
3. To keep your auto-complete list useful, you might want to enable the option for Outlook to automatically create contacts by putting them in the "Suggested Contacts" address book. (Outlook 2010 > File > Options > Contacts > Check the box for "Automatically create Outlook contacts...." > Click OK. Then, as often as you like, you can run NK2Edit and ADD the contacts from Suggested Contacts to your existing NK2/DAT file.
==============
==============
I hope this helps some people. At the very least, I hope it helps others to understand the problem better. If you have any additional tips/comments/questions feel free to comment here and I'll do my best to write back!