Although optimizing is important, don't worry too much about the specific case of someone trying to abuse it. If someone wants to slow down your server, they will use a [D]DOS attack (which is much easier than trying to find an exploit), in which case the queries in your message center will not matter anyway.
Anyway, you could take a "threaded" approach: the first message of a reply-chain becomes the "replyid" reference for all subsequent replies. Then the replies are fetched in a single query which orders them by date. This is the approach that forum threads use, as well as GMail conversations. However, in order to list them in the inbox, you will need a join query that orders the thread by the time of the last reply.