Plugins are often the culprit
Have you tried disabling all plugins and testing your speed there? Usually the inefficient code that can affect a site this significantly is in a poorly coded plugin. If you are still seeing problems, disable all and see if you get a significant change in performance.
Since you are using good caching tools (make sure you have them set up correctly and they aren't fighting each other), the culprit for your main issue is almost always going to be in a bad query somewhere. The folks who code the core of quality CMS's like WordPress and Drupal typically do a great job - not perfect, no code ever is, but core CMS code is going to be superior to plugin code 9 times out of 10.
Sometimes too many cache schemes/tools can work against you
Try Varnish, but not at the same time you have memcached eAccelerator, or xcache enabled. APC should be fine but be mindful. Varnish is a reverse proxy cache that intercepts a request before it gets to the application if that page has already been loaded, and it has given me some fantastic performance increases.
You may want to go into your W3 Total Cache settings and instead of just enabling all of the options try some different combinations. DB caching is usually quite helpful, and APC opcode cache is almost always good for a 35% performance boost but only for the php side of the LAMP stack.
Get your static files on a CDN (Content Distribution Network).
W3 Total Cache has a setting for CloudFlare and I gave it a shot on a slow site. There is a free tier and it still does the job very well for me. They will ask you to change your DNS servers to theirs, that isn't a big deal. It will simply allow them to host your media files and other types of content on a blazing fast server that has geographically distributed access points, reducing the number of hops. It's not precisely applicable to your database issue, but I will use any cost effective (aka free) improvement I can find, and it make a difference.
To use CloudFlare, simply create a free account or upgrade to a higher service level (adds features, not speed) and then all you need to do is follow the directions and plug your API key into the appropriate box in the W3 Total Cache settings page.
PS I have no stake or interest in cloudflare, I'm sure there's plenty of other services, but the integration with W3 Total Cache makes it pretty darn simple, and I was very impressed with the results.