IDP initiated login

Users consistently see the error when logging in via AD IDP:

“You may have pressed the back button, refreshed during login, opened too many login dialogs, or there is some issue with cookies, since we couldn’t find your session. Try logging in again from the application and if the problem persists please contact the administrator.”

This only happens on AD and happens every time. This does not happen with other SAML providers.

Any suggestions on what may be causing this and how we can debug it?