The Address Book issue should be an easy fix.  It's a common occurrence when
moving things around -- the association between the Contacts folder and the
Outlook Address Book gets broken.  To fix it, go to Tools | E-mail accounts,
select "View or change existing directories or address books", and click
Next.  If you don't see the OAB in the Directories and Address Books list,
click the Back button, then select "Add a new directory or address book",
then "Additional Address Books", and add the OAB.  Then keep clicking Back
until you get back to the first dialog box, and go back to the Directories
and Address Books list as you did earlier.

Once the OAB appears in the list, select it and then click Change to make
sure the Contacts folder(s) you want to display are listed.  If any of them
aren't listed, you'll need to enable those Contacts folders as Outlook
Address Books by right clicking the folder, selecting Properties, clicking
the Outlook Address Book tab, and checking the "Show this folder as an
E-mail address book" box.  Make sure you restart Outlook after making these
changes.

As for the missing e-mails:  Are you using the Activities tab within a
contact record to find the messages associated with that contact?  If so,
you should be seeing the folder name that each message is located in.  If
you're not using the Activities tab, how are you calling up the list of
messages?