To be more precise, Facebook knows hash(random_salt, facebook_password), and could do a check on the actual facebook_password when a user logs in, but I assume that it's not stored. Everyone knows encrypt(key, adobe_password), since that was what was leaked, and presumably adobe still has the key, so they know adobe_password.

Facebook wants to determine if facebook_password == adobe_password. Without the key, that's impossible. And I think 112 bit keys as provided by 3DES are still secure, even considering an adversary with the resources of Facebook.

A lot of the articles analyzing the adobe passwords seem to be comparing known-common passwords, passwords hints, and the insecurities of ECB-mode, which doesn't really scale. It seems like it would be better for facebook to just have a blacklist of common passwords (123456, password, etc), although then I suppose they don't get credit for pro-actively responding to a password leak (note: I'm not claiming that's why they're doing it - it seems like a good response, and I'm genuinely curious how they're doing it).

Edit: I just thought of way they could do it. Generate a histogram over the first 8 bytes of each encrypted password. Pick a threshold (e.g. 2, or 10, but you'd have to look at the data to get a good number) above which the password is considered "common" and therefore insecure. Go through the list of email addresses in the adobe dump that have a "common" password, and if there's a facebook account with that email address force a password reset. That seems like it would work fairly well, and doesn't require any knowledge of the plaintext passwords.