Know what? Maybe the attacker is logging all the passwords that are entered. Maybe they installed a passwordless backdoor. Maybe they installed spyware on all your users' machines. There's very little point discussing all the imaginary attacks which may have already happened that you don't know about, that could be anything.
What would a password bankruptcy pattern look like?
One thought is to invalidate all passwords and fall back on email password recovery when a login is attempted.
This leads me to an idea I've tried once - if access to the inbox is equivalent to password credentials, why not use an email to login? By this I mean the web site login is a single field - email address. The system emails a one-click-login URL to the user that can be re-used (possibly with a month expiration time). The user can look up the URL in their inbox when they want to login again, or use a long-lived cookie.
I have lots of logins tied to email addresses no longer in use. As a real world example, people sign up for services with work emails. The day they get fired, they suddenly lose access to that email and all of the email login services tied to it. Not good.
I think a better idea would be to establish an easily implemented pattern for "password bankruptcy" that companies could follow in the case of a leak.