By default Outlook 2010 caches email addresses that you have used when sending out emails. In Outlook 2007 these addresses were stored in %USERPROFILE%\AppData\Roaming\Microsoft\Outlook\*.NK2 . In Outlook 2010 they are now stored in a file called: %USERPROFILE%\AppData\Local\Microsoft\Outlook\RoamCache\Stream_Autocomplete_*.dat .
An issue I have seen is when Outlook 2010 is closed, the Stream_Autocomplete_ .dat file deletes. When this happens, Outlook will no longer auto-complete your email addresses names. To correct this issue you simply have to toggle the option of using the Auto-Complete List off and back on again.
Outlook 2010 > File > Options > Mail > Send Messages >
- Press Empty Auto-Complete List (just for good measure)
- Uncheck Use Auto-Complete List to suggest names when typing in the To, Cc, and Bcc lines
- Press OK
- Exit Outlook 2010
- Re-open Outlook 2010 and Re-check the above option and OK it and exit Outlook
That has solved the issue for me and I have never had to rebuild the mail profile.