We've enabled CDN cache (Cloudflare) on several pages and noticed, on the rare occassion, the Episerver Menu is visible in top-right corner when the page is served by CDN cache.
I suggest Episerver update their menu so it's only visible when the forms login cookie is present. In the meantime, we'll use the Bypass Cache on Cookie setting in our Cloudflare page rules.
It sounds like you enabled the "Cache Everyting" option in Cloudflare and the first visitor to some of the pages were logged-in users. Then Cloudflare caches the page as rendered with the Episerver Quick Navigator Menu shown.
This issue has nothing to do with Episerver. Since you instruct Cloudflare to only send the request to Episerver once in a while, Episerver would not know when to display the menu or not.
As I see it, you can either: