Personally I would design my tables like this -

Table: Messages
message_id	recipient_id	sender_id	message	date	status
1	500	501	hey mike	2003-11-02	NR

Primary key: message_id
Foreign keys: recipient_id, sender_id

Table: User
id	nickname	fullname
500	bob	Bob
501	jane	Jane

Primary key: id

So when user bob logs in, the SQL to check for new/unread messages would be like this -

SELECT *
FROM messages
WHERE recipient_id=? AND status='NR'
[download]

After Bob has seen the message (assuming that the message id is saved some where on your web page (hidden field perhaps, or a session variable) -

UPDATE messages
SET status='OK'
WHERE message_id = ?
[download]

And when Bob replies a message back to Jane -

$msg = "original message"; # assume this is from the prev message

$reply = $newmsg . "\nOriginal Message\n------------\n" .
         $msg;

# and then just insert the reply into messages table with SQL insert

INSERT INTO messages (message_id, recipient_id, sender_id,
                      message, date, status)
VALUES (?, ?, ?, ?, ?, 'NR')
[download]

And for the sequencing of message_id's, I normally use a database trigger on INSERT, that queries the table searching for the maximum message_id, add 1, and set as the new message_id. If you don't want to use triggers you could certainly do this easily with SQL and a bit of Perl.

Ok, what could be tricky is when multiple users are trying to send messages to others at the same time. For that you need to implement proper locking mechanism if you don't use DB triggers, and that's one occation where I think DB triggers are quite useful. And you certainly would need to handle insert exceptions and try again if necessary.