lost my password link gives invalid key every time

Hi there,
We’re running a Multisite installation with about 60 sites and 400 users. Currently, the “Lost Your Password” link on all login pages – for any site in the network – does not work. If the user clicks on the link, they are asked for their username or email, and they are sent the email, but when they click on the reset password link, every time, they get an invalid key error when they try to save the new password. (here’s what that error looks like: Screenshot of error message)

I’ve tried every solution I could find on these boards: generating new auth unique keys, turning off plugins, reverting to the twenty fourteen theme, editing the wp-config.php file, etc. etc. and nothing is working. We are NOT using any caching plugins or the Theme My Login plugin (which has seemed to cause this issue in the past.)

I’m stumped! Has anyone found a solution for this? It isn’t sustainable for us to manually change passwords as our users need it.

Thanks,
Carrie