Thanks for your in-depth reply and suggestions.
MySQL performance tuning and table structure/query optimization-wise, we've left few stones unturned (but I'm sure there still is a scope for further improvement - isn't there always?).
Not using Rails.
Server specs: 4 cores, 3.2GB RAM
>and the easiest route is just to upgrade your server.
Please refer to the other thread for more on this.
Thanks again.