Themekey 'Retain the theme until a new theme is set' setting not working with cached pages for anonymous users

I have a content type called announcement. I have configured this content type to not have a theme applied to it, but to allow ThemeKey to apply the theme based on the
theme of the previous page. Incidentally, the announcement content type is configured to never be cached (via CacheExclude)

I have theee mainpages for my site, each with a different theme. If I cache my three main pages for my site, themekey will not properly set the theme for announcement links off these pages. If I remove these pages from the cache list (using CacheExclude), then themeKey applies the theme just fine.

It is possible for anonymous users, the only page they hit on visiting my site is one of these three main pages, before they click on an announcement link. If these pages are cached, is there a possibility that whatever function that set's the previous page theme does not get called and themekey does not know what theme to apply and just applies a default theme for these users?

I know the workaround is just to remove these three pages from the cache, but these pages get hit a lot and account for 50% of all my site traffic, so I'd hate to remove them from the cache.