It would be very helpful to be able to do a text search through all of one's private conversations. That includes in- and out- mailbox messages, but also all messages exchanged during games.
Sometimes I remember having had a nice conversation with someone about some particular subject, but cannot remember who it was, or I remember the old handle but the user now has a new one.

Of course it would also be helpful to search across all discussion boards (including fellowship boards), but that is a different search. Usually one remembers very well if somethings comes from a public board or a private conversation.