Reinstate the use of memcached, at the object-level. Rather than storing things on the localhost each server would talk to the central memcache instance. That would avoid each of the webservers from having a local, and potentially stale, cache.
The other way to go would be more fine-grained caching with varnish. Right now we cache in-RAM as much as possible, and on any event which can change the state of the site (new comment posted, new article posted, etc) we throw away the _whole_ cache. That's quite a heavyweight solution, but it was fast to implement and is provable to never leave stale content around.
(I once setup a site for a friend where we did the same thing; the whole site was cached, and the cache was blown away every time a POST request came in. That worked perfectly, and inspired me.)
Using the varnish PURGE requests though we could uncache only the things that have changed. The reason why I didn't go down that road is because there are non-obvious dependencies. For example if there is a poll vote the front-page must be thrown away, because it has a running total of the votes applied. Keeping track of all the things that should be expired on a single event would be a headache.