What did you do to lose them? Outlook doesn't do it on it's own, so there's
more to your story. You did something to disconnect your Contacts from the
MAPI addressing service. Moving, exporting or importing your data are the
most common ways to cause this problem.