BLOCK_NO_CACHE with Normal page cache enabled I'm trying to create a block, which shouldn't get cached, even for anonymous users. But there's "Normal" page caching enabled on the website. As I've read in various places, the BLOCK_NO_CACHE setting doesn't really count for anonymous users when page caching is enabled.

As it stands, it's not an option for me to turn off the page caching, as the website receives moderately high traffic. 

I've first tried injecting some HTML with hook_footer but this function doesn't get called as well when page caching is enabled.

The block I'm trying to implement is a very simple one, it only has a bit of text and a link, which upon clicking, sets a cookie on the user's browser (with PHP), and returns the user back to the page where they clicked the link on. Upon returning to the page, the block needs to attempt to read the cookie, and if the cookie is set, the block should no longer be displayed.

However with page caching turned on, if AnonymousUser-A clicks the link and no longer sees the block, then AnonymousUser-B comes to the site, they also don't see the block. 

Is there a workaround I can use to get around this issue? As you can see from my use of hook_footer, I'm not heavily inclined to implement this as a block. Any solution that will fit the above purpose is welcome.
Ajax Blocks or Ajaxify Regions (since you're in D6) allow dynamic blocks within cached pages.