Hmmm...
Off the top of my head, untested:
Code:
SELECT M1.id, M1.to_id, M1.from_id, M1.message, M1.`date` AS originalMessageDate,
MAX( IFNULL(M2.`date`,M1.`date`) )AS lastReplyDate
FROM messages AS M1 LEFT JOIN messages AS M2
ON M1.id = M2.original_messsage_id
GROUP BY M1.id, M1.to_id, M1.from_id, M1.message, M1.`date1
ORDER BY lastReplyDate DESC
If you want to also pick up other fields from M2 (the latest reply) then it gets a bit more complex.