I bypass this problem by not allowing failover. As long as losing a server and getting it back results in the server losing all of its contents, there shouldn't be anything floating around that should have been deleted or expired before.
This does mean that while server A is down some percent of requests will always be cache misses, but we have enough servers that it's relatively low and it doesn't do much harm to the database.
