I don't see how rainbow tables are relevant. How would you use a rainbow table to crack passwords encrypted with an unknown key?

You couldn't. It's not possible. If you don't know, then it's not possible to pre-compute. Many people fail to understand that. Rainbow tables (while sounding magical, are not).

Edit: But they are great for standard unsalted hashes. md4, md5, sha1, sha512, etc.