Those size constraints are based on the concept of storing every password and its hash in the table. However, that gives a reverse lookup table, not a rainbow table. The key to a rainbow table is that you look at an initial password, hash it, use the hash to generate a new password, then repeat a few thousand times. Then you store only the initial password and the ending hash. To use the table, you do the same thing, but check each of the intermediate hashes against the rainbow table; if you find it, you start at the initial value and follow the chain until you get the password.

So, of the OP's points: 1) Storage space: cut by a factor of several thousand. Assuming that you're OK with chains of 50K passwords, that's only about 1T total for something that will (probably) cover most of the password space. 2) Hash algorithms: If you're using a single SHA256 to hash passwords, you're doing it wrong. SHA256 was designed to be fast. Real password hash algorithms are much, much slower. 3) Salts: As AppSec says, most sites screw up salts.

So, while rainbow tables aren't that useful against a properly secure system, they still have their uses.