>Not even sending a token to the email address on file would work in all cases because the users might have lost their email accounts to the breach too (by reusing the same weak password).

Well, in that case, it'd be the user's fault for not having unique passwords, or at least for not changing an email password they knew was compromised, not Sony's fault. Sony can't do anything to ensure the users' email accounts are secure, so emailing a token would probably be the best solution.