Hmmm. I might be missing something here, but I routinely clean out cookies in "public"/unauthed URLs in Varnish, as well as hashing the cache based on _part_ of a specific cookie (the bit that defines, say, the site's theme, or a generic user role).
They do mention that they didn't investigate how to do this in Varnish, but I recall having picked up the basic technique from one of the author's posts.