Private Messaging with ability to delete and reply

I’ve set up a few PM systems in the past and I always make it so each user has their own message table. This allows them to perform edits (such as deletion) on their messages. However this seems like it could be a problem if there are alot of users. What mysql configuration would I need, or is there a better solution just using just a few tables to handle all of the users messages.

put all the messages into a single table, and make sure it’s innodb, so that inserts and deletes will not lock the entire table