In a WS-Fed scenario such like yours, SharePoint is supposed to redirect the user to ADFS for authentication and then the user POST a token back to SharePoint (assuming that the authentication was successful).
If SharePoint accepts it, it creates a bootstrap cookie and that cookie is used for further access.
If SharePoint doesn't accept it, or the token isn't valid yet (case of time sync issue between the SharePoint servers and the ADFS servers) or if it cannot make use of it, and can't create this bootstrap cookie, then the user is redirected to ADFS again to obtain a valid token. There is also a known issue if SharePoint rejects tokens which are about to expire. If you reduce the default token lifetime (which is 1 hour) to something a bit too short like few minutes, in that case even a brand new token will be rejected because SharePoint wants something valid for longer. But that's a corner case and all users would be affected.
Now if clearing the cookies sometimes fixes the issues, it might be an issue with the cookie manager of the browser. Or the cookie is too large and can't be processed. I don't know what SharePoint puts in the cookie. But if there is the group membership information in it, that could explain the size and why not all users are affected. But that also depends on what claims you send to the SharePoint to start with.
If you capture (sanitize and share) a Fiddler trace, we can maybe narrow down this cookie mystery.