Rainbow tables haven't been too relevant for a few years now. The problem is (1) they're really large, and therefore hard to move to a target computer and (2) anyone serious about password cracking has a GPU farm that can essentially recreate a rainbow table within a few seconds.
The last time I looked at this, a modestly-sized GPU farm could try all passwords up to length 6 in 1-2 seconds. This means that encoding those passwords into a rainbow table would really not make that much sense. Moreover, as you pointed out, most passwords are salted anyway, meaning we'd need rainbow tables for each salt value, and for larger salts this is completely impractical.
I can't imagine too many scenarios where rainbow tables might be the best choice. Perhaps a casual cracker who can afford the terabytes needed (drives are cheap) but cannot afford to build a cracking cluster, and who has the time to download the tables (or have them shipped via DVD).
That said, reasonable improvement to the algorithm would probably still be publishable. As long as your improvement isn't completely trivial.