I'd probably implement the database something like this:

CREATE TABLE messages(
  msg_id    INT         NOT NULL PRIMARY KEY AUTO_INCREMENT,
  parent_id INT         NOT NULL,
  status    VARCHAR(3)  NOT NULL,
  from_who  VARCHAR(30) NOT NULL,
  to_who    VARCHAR(30) NOT NULL,
  sent_when DATETIME    NOT NULL,
  msg_text  TEXT        NOT NULL
);

CREATE TABLE users(
  user      VARCHAR(30) NOT NULL PRIMARY KEY,
  # etc, etc.
);
[download]

Upon an original message (non-replies), you insert the following into .messages. Note the -1 value for parent_id. This is an indication that this message is a parent message, not a reply to anything.

INSERT INTO messages VALUES(
  '',-1,'NR','Coruscate','perleager',NOW(),'hello there!'
);
[download]

A reply to this message would be inserted as follows. Note the parent_id field. This would be the id number of the message that is being replied to.

INSERT INTO messages VALUES(
  '',10932,'NR','perleager','Coruscate',NOW(),'hello back!'
);
[download]

To display a message in its "thread-like state" (showing the entire 'conversation'), you simply throw together a method that looks at the current msg_id, then recurses through itself to propagate up the history tree.

The 'NR' I used is borrowed from another reply to this node, which I assume stands for 'Not Read'. To delete a message with this database setup, you wouldn't be able to actually delete the entry from the database until all sub-messages of that message are removed as well. My solution would be to set the 'status' column to 'DEL' when a user deletes a messages. Your code would then see to not display this message in the inbox, but the data would still be available to add to the archived thread-like state. Add a cron script that rips through the database every so often and actually deletes info from the database by being smart enough to find entire "threads" that have been deleted.

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

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

$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]

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

Oooooorrrr... you could just add an auto_incremented message_id field and let the database handle the incrementing mechanism. :)

Well, that could be really nice, but I am using Oracle here that doesn't have this feature unfortunately. :-(