I noticed the message table is not indexed by anything other than mid (foreign key on uid and message_type, but no indexes).
Because we're often going to want to fetch messages for a given user, or fetch messages by age (which will not necessarily correlate with mid) it makes sense to index the message table by uid and by timestamp as well.
This falls in line with Drupal best practices, as for instance, the node table indexes on uid and node created time (actually, the node table indexes on every column). Makes sense to index by message_type as well.
I would say this should be a major priority from a performance standpoint.