PHP-MYSQL messaging system performance problems
You can use a database such as mySQL just fine. Especially if the table structure is simple and indexed well.  I would presume a record for each message would create a need for inserts, but not updates, which would keep index rebuilding needs low too.

If you wanted to scale, just create a read-replica for the querying of the messages and send the write queries to the master server.

Want to scale even more, I suppose you could implement some sort of memcached intermediate level, but this would help more on expanding performance on the read side, not the write side particularly (since you'd have to write them eventually, and you could lose them in memcached in the interim potentially).

In short - mySQL is fine.  Other options include cloud options from amazon like DynamoDB and/or nosql options, but not essential.