It's not the algorithm that's difficult, it's the effect of adding caching to a system that wasn't built with caching in place at the start that is difficult.
This isn't an "urban legend" it's first hand experience working with companies trying to add caching. No, those companies aren't even trying to write caching algorithms, they're just bundling in a caching layer and hoping that the system behaves in the same way.
It only takes somewhere which writes data (perhaps in a way that bypasses the caching layer so the cache doesn't know it has changed) and re-reads it back quickly for software which used to work suddenly breaks.
Now you might look at that and go "omg refactor it! That's horrible code, that should never ship" etc, but not everywhere is the s.v. bubble with endless amounts of the best developers to throw at problems. Code which worked and solved a business problem ended up shipping, possibly without testers and probably without code reviews.
So adding a caching layer suddenly "breaks" those reports, now who's going to have to fix it, not the person who wrote those reports even if the very behavior of side-effected data changes and db re-reads is precisely a cause of data layer slowness that led to wanting to implement caching...