I used Windows Live Messenger quite a bit at work this summer. You can save message logs in an xml format (enable this in Options). There is an xslt to view the logs in IE, but I wanted something cleaner.
So, I put together a quick app in Windows Forms. (You'll need the .NET 2.0 framework). It doesn't do much, but it does have search. The main interest for me was to use the XmlTextReader (a very nice lightweight xml reader built in to .NET, perfect for this task). I was also interested in RTF; instead of the methods for formatting, I set the raw RTF of the RichTextBox. The result is a useful little app, thanks to .NET. Source and binary (68 k).