ti trovi tutte le coppie "univoche" di sid e rid e poi per ogni coppia peschi l'ultimo messaggio:

codice:
my recordset = select sid,rid from messages group by sid,rid;

while not recordset.eof
do
   my last_message = select message,time,check from messages where sid = recordset.sid and rid = recordset.rid order by time desc limit 1

   print last_message

   recordset.next

loop
per velocizzare la cosa ti puoi fare una store procedures dentro mysql che ritorni un set di row con sid,rid,last_message,last_message_time,last_messag e_check in maniera da fare una query sola da php...sostanzialmente traducento quello pseudocodice in linguaggio sql e passando i giusti parametri.