Shall we assume you do not use an LDAP? If so, then remove it as an address
Service and add the Outlook Address Book Service instead.
You've posted no Outlook version, so I'll assume you don't need to know how.
I suspect you installed Outlook as an upgrade but failed to create a new
profile after you did. http://support.microsoft.com/kb/836205/en-us