I know that in outook there is a feature called the JOURNAL that keeps track of e-mails and such. I'm not sure if you have it enabled, but you should at least be able to see what recent messages were sent or received from different contacts. First thing to do is see if the journal is turned on, click on TOOLS>OPTIONS>JOURNAL OPTIONS and that should allow you to determine what's being journaled. Then to see the results of that, open a contact and click on the ACTIVITIES tab and that should start a search through your folders and journal for applicable items. You can also add entries regarding phone calls and such. To do that, right click on the contact and select NEW JOURNAL ENTRY FOR CONTACT and that will allow you to enter notes that keep track of dates and times.
Do be aware that although outlook has some nice functions that most people don't use, it's not really a replacement for a full CRM package like Act! or Goldmine. It does, however, work nicely with the other applications in the Office suite.
Almost forgot one REALLY IMPORTANT THING and that is you need to make sure you DON'T DELETE the messages that you're interested in "linking" to your contacts otherwise when you go to activities, it won't show up. Pretty common sense I realize, but I had a client get a little pissy with me because I didn't specifically tell them that. Of course, as I try to tell my clients I can't be responsible if they don't take the time to learn the software and they do something stupid. I'm no software developer or anything and my knowledge of the software comes from my own use and experimenting.