Aha, now it's clear. I don't think that is a core WordPress query. With so many posts, each time one is added it will grow. The plugin or theme function executing this query is obviously not one that is good for production environments. You need to find the code causing that and optimize it. For APC the SHM size can be increased easily, for memcached you can recompile to increase slab size. In either case, I do not recommend it as there is no performance win there, that query is not productive. Also spreading out queries amongst too many memcached servers is not a performance win. 1 or 2 instances per cache type is already enough. Just make sure you use memcache. And if possible use APC instead as it will be faster in general.
Anyway, this is not an issue related to W3TC, caching cannot improve all queries.