We're not using any page compression, but I've found the likely cause of the issue in our case:

Disabling the Host Caching option didn't make any discernable difference, but changing it from Heavy Caching to Moderate did.

It looks like our shared server can't cope with the heavy setting, and that the banner issue is tied into application recycling. So far, on the moderate setting, the longest "banner outage" I've had has been 5 minutes, so it's a huge improvement, if not a complete fix.

Still not sure why an application restart didn't have any effect - the memory cache doesn't persist after a restart, does it?