First of all, check the Outlook Integration is enabled in Personal information manager, in MOC properties.

and Make sure that you should have Only Default Profile configured for Outlook,
and make sure that your  SIP ID and Email ID both are same.

Thanks,
M.Ismail.

Outlook Integration is enabled in Personal Information Manager in MOC. There is only 1 profile in Outlook.

As far as the SIP ID and Email ID; they are different.   We currently run OCS in a seperate 2003 Domain environment (for this purpose- now called GROUP-A).  The Computers that are not saving conversation history are in a 2008 domain environment (different forest, and for this purpose called GROUP-B).  There are trusts between the 2 domains.  

We recently upgraded the GROUP-B from SBS 2008 to Server 2008 Enterprise R2.  Complete re-build. GROUP-B's conversation history was saving without error in Outlook when on SBS 2008.  After moving to Server 2008 Enterprise R2 nothing is saving.  And just to re-iterate the SIP ID and EMAIL ID are different.  

Although you might say that it is because of the SIP ID and Email ID it was working without a problem before the upgrade.

I apologize if this is confusing.  If you have any questions please let me know.

For More Info refer the KB Article below,
http://support.microsoft.com/kb/2018725

Am Sorry, Please Ignore teh above comment, it was posted  by mistake.

Do You get any error e.g.like "Outlook Integration error" ?

No I am not recieving that error.

Thanks ismailshaik02 I believe that resolved my issue. I have tried it on a Client running Windows 7and it resolved the issue. I have 2 clients still running Windows XP that I need to verify before I can accept it. I will have it tested by the end of this week.

Thanks again

Okay It worked on all computers running Office Communicator 2007 no matter the OS.  

However I have one client running Office Communicator 2007 R2; WIN7 Pro SP1 x86.  (He is an admin and I didn't know he upgraded it).  I went to change the value in his Registry however the Communicator folder is not listed under HKEY_LOCAL_MACHINE\SOFTWARE\Policies\Microsoft.  Is it in a different location for Office Communicator 2007 R2?  I looked around and couldn't find anything similar.  That is the only difference that I see that may be causing this issue.

SInce he is an Admin per your comment,
Check out he might have installed some Admin Tools or Exchange Management Console in his profile,
if its there it has to be removed from the system, also check for any multiple profiles in out look is configured.

Also if the Key doesnot exist creat one as it is.