First of all, wow, thanks for all this answers/hints. I know that my question looks like some really bad design decisions have been made, which is probably true btw ;) The applications im talking of, is built on a big legacy database, which makes it hard to modify the datastructure (and yes, the query is only using indexes, no unnecessary sequence scans). It's just not designed for such types of queries.
But you (almost) conviced me, that it's probably better to populate some database tables which are designed for this application from the legacy database and just use memcached for what it's designed for. Either way, I will have to add some complexity by populating a separate database or warming the memcached cache in the background. So I think it doesn't really care from that point of view. Cheers.
