Thanks everyone for the additional info!
It definitely sounds like Health Check is linked. I've never set up, or used Health Check, so it is one of those features that wasn't suspicious to me originally. One feature that I thought might be related was that CCleaner, at some point, added CCleaner cookies to the excluded list of cookies by default, but when I removed that entry from the list this problem continued.