I created a new profile but it did not resolve the problem.

This bug can be consistently replicated:

1. Select “Data File Management” in File menu
2. Add additional Outlook Data file than contains contacts (which causes an
error and restarts Outlook)
3. When Outlook restarts
a. New personal folder appears below existing personal folder
b. Error message window appears: “This information service has not been
configured. Select an existing file to configure, or type the name of a new
file to create” OK
c. When OK is selected “Create/open Personal folder file” panel opens up
d. Select any .pst file
4. Goto Contact tab. Select Contact properties of the newly added folder
file. Select “Outlook Address Book” and check “Show this folder as an e-mail
Address Book” and select apply. Then uncheck “Show this folder as an e-mail
Address Book” and select apply.
5. You can now open a new mail message and select “To. . .”. The address
book will now open.
6. In addition the address book on the main Outlook string will open when
selected.
7. The Outlook address book will continue to work until Outlook is closed.
After Outlook is restarted the Address book will again not be available and
the original error message: "The messaging interface has returned an unknown
error. If the problem persists, restart Outlook." ok is displayed.