Seconded that cache-invalidation is hard. This may be a cliché, but it really is hard.

Implementing a cache may be easy but debugging a cache, or particularly the interactions of multiple caches (some outside of your control) certainly isn't. I've encountered these problems on many projects and also written about them in detail for my recent book.