I had a situation where users were (seemingly) randomly being prompted to log into the CMS when visiting a page that is public.
The solution was to completed clear the entire cache for the site. Once we did so, the login prompts went away.
Has anyone experienced that before, and if so - did you ever find the root cause of it?
Without knowing your setup/config and what promt it was, it is hard to say anything, but it sounds like you once had Cache Everything on, so this promt, may was cached and served to the user. So could be a cache missconfiguration.