Outlook won't populate the auto-complete cache automatically but it’s a fairly simple task:
Open a new message and click the To button, select all of the names in the Suggested Contacts folder and add them to the message. Repeat for your Contacts folder. Close the message without sending.
This method works in all versions of Outlook that use autocomplete.
Note that there is a limit to the number of names you can have on the autocomplete list. In Outlook 2003, it's 1000. In Outlook 2007 and 2010 it's 2000. In all versions, it's an MRU - most recently used - list, so frequently used addresses will always be on the list.