Chances are the e-mails they've been sending so far went unread/got moved to spam by a lot of users and Gmail took that as a signal.

I send nothing but password-reset mails and never had an issue getting anything delivered, even though people constantly whine that delivering e-mail yourself has gotten so hard nowadays.

Just got a clean IP and don't send crap.