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.