I submitted the bug to Microsoft's beta place. I guess they should already know about it by now (sure you are not the only person on earth with big Message History's).
I wonder: how big are your MSN logs for the person on which you have the most problems and how fast is your PC (MHz/GHz and RAM) ?
I will post here if i hear anything about the report, i the meanwhile i would suggest do disable MSN's Message History and use Messenger Plus!'s Chat Logging feature
.
/ 
