This is pretty basic, but in addition to mysql table structure and query optimization, have you done/considered any tweaking of the mysql config itself? (Usually at /etc/my.cnf)

We've repeatedly experienced huge performance gains even with basic/minor tweaks of my.cnf.

HTH