I am not a database-expert, but here's a solution that might work:
Since you already have sender and receiver in your table, you already have some kind of ID. You could use timestamps to identify messages that come from the same sender to the same receiver. That has some really cool effects: Even if there is more than one user sending messages, you're still able to print them in the right order. And you don't have to worry about deleted messages. What type of timestamp you use (EPOCH or human-readable) shouldn't really matter. The important part is the timespan they describe. And that depends on how often your users log in. If you use timestamps that identify the month that should work fine.

I hope that could help..
Regards, octopus
--
GED/CC d-- s:- a--- C++(+++) UL+++ P++++$ L++>++++ E--- W+++@ N o? K? w-- O- M-(+) V? !PS !PE !Y PGP+(++) t-- 5 X+ R+(+++) tv+(++) b++@ DI+() D+ G++ e->+++ h!++ r+(++) y+