Perhaps a solution would be to decentralize it. This would probably require creating a program much like folding@home, however... have each node in the network be able to talk to other nodes in the swarm. This would be a big project of course, but it would enable the community to go on, without a central repository for the master rainbow table. Anyone who actually has the knowhow to do this can look at the gnunet project (gnunet.org) for ideas (or perhaps just base it on gnunet :P). Another program in development now that has some good ideas for using a P2P network for uses other than filesharing is okopipi (okopipi.org).
Just throwing an idea out