The function message_search() in message/lib.php could do with some enhancements.
1) It doesn't seem to limit the maximum number of search results that will be retrieved. Either implement paging and show say 20 records at a time or simply cap the results returned to 100 or so. Either way pass the limits in to $DB->get_records_sql() to limit the size of the result set at the database level.
2) Also, single letter search terms are culled from the array of conditions. This is to exclude search terms that may bring in bogus matches. For example "a brown dog" will be split into "brown" and "dog" with the letter "a" being discarded. This has the side effect that if the only search term is a single letter it is discarded and the following default where clause is constructed.
m.fullmessage like %
This will match every message which probably isn't intended behaviour. I'm guessing that if the search term consists of only a single letter we should still be searching for it even though that will return a lot of results.