How to invalidate a views cache based on custom criteria?
It sounds like the problem is not views being cached, but that the entire page is being cached. If Drupal have a complete page cached, it doesn't matter if the view is cached or not. What you need to do, it to conditionally disable the page cache, or prevent Drupal caching that page in the first place.

There have been some talk about how to do the first, but this is not something I have tested or can advise.

Be warned, that messing with the Drupal caching system can give some unforeseen problems.

An alternative solution would be to empty the page cache or invalidate the cache for that particular page once a day/hour to make sure that it's relatively up to date. This is probably the route I would take in this situation.