The configuration of the mysql tables actually makes a pretty startling impact on performance. If you're using myisam on a table that is both written to and read from a lot like character_ it can really bog things down with all the locks going off left and right.
Tell / Combat lag could happen if it's bogged down from the database but it would be intermittent: not every tell would lag for example just the ones that happen during a slow query. Oh and I guess you could turn on
http://dev.mysql.com/doc/refman/5.1/...query-log.html and see if there are any queries really causing problems.