"Incorrect or out of date key"

Hey,

I have a major problem on my multisite. People with mapped domain often experience that when trying to visit their site, they just get the message "Incorrect or out of date key".
I have read here: https://premium.wpmudev.org/forums/topic/incorrect-or-out-of-date-login-key#post-737147 that it would help to clean cookies, but I don't know how to do that for my whole multisite installation.

Please help, this is driving me and my users crazy!