The number of generated key pair to find "facebook" + keywords must have been gigantic, maybe even so much that it could be used as a kind of rainbow table which would allow people (or three letters agencies) who can access it to attack hidden services that use one of the .onion for which a corresponding private key is known.

Relative to the 2^80 (1,208,925,819,614,629,174,706,176) possible onion addresses, whatever they generated would be miniscule.

Indeed. I was being stupid and didn't take the time to really think it through. Thanks to you and all the others who pointed that out :).

Presumably those 3 letter agencies also have the technology to generate RSA keys.

Nope. They ran a cluster to generate billions of addresses, and used some logic to find a nice one. But that won't help them a bit to find a specific address, since all the addresses they generated are only a vanishingly small fraction of the possible addresses.

This was a huge discussion on the Tor blog or subreddit. It was concluded that it is unlikely that they even found one existing key.

If that is indeed tractable for a side project at Facebook over a few weeks, it's definitely tractable for someone who actually cares to attack Tor.

If I understand correctly finding an "equally good" domain name starting with facebook<something> should be equally possible yes.

Finding that same one again? Not likely.

This is not vulnerable to brute-force nor rainbow tables.

That shouldn't matter. If the scheme is vulnerable when some company generates a bunch of keys, it is vulnerable whether those keys are deleted or not.