I don't know if this helps you, but, if you have a unique identifier in your "message" table, then you could just add a "replying_to" field in your "reply" table. THEN when someone is replying to a message you could pass that unique identifier into the replying_to field (through hidden field on form or another query on the insert).
When you, later, do your query of messages to show on your message board you could just do a select where replying_to = message_identifier. IF there is a match then you increment $counter by one and show # of replies, or actually show the titles depending on how you are threading your board.
I did that with my message boards and it worked out okay.
Are you storing the message IN the table? I just stored the title to the message table and wrote out the message to a text file, that way someones garbled HTML will only appear on their message page. Just a thought.
