Timing attacks are a problem when the server is checking a value the attacker can control bit-by-bit. Hashed values do not meet this requirement.
Rainbow tables don't seem like a very applicable technology for this. I think you'd want to pre-process a dictionary of passwords you want to be able to guess (either from known passwords or just obeying some rule) so that you can group and order them by MD5 prefix.
Using the oracle lets you narrow down 50% at a time, so if you've got a dictionary of 1 billion passwords, after 30 iterations you've either rejected all the possibilities or found a correct password.
NB This makes no difference against a strong random password, since a hypothetical dictionary of such passwords is far too large, it only impacts ordinary human passwords that you could brute force if you had the hash.
Using such a table would allow you to select guesses that matched the first n bits of the stored hash and then use timing to try to guess the right choice for the n+1’th bit... up to the first 64 bits. You would then have limited the number of guesses down to just another 2^64 possibilities. So that’s not really a valid approach.
A different approach would be to try to figure out the first ~32 bits of the hash using a much smaller (34GB) table and use that knowledge to screen potential candidate passwords offline.
Again, all this works only as long as there isn’t a salt, and the value you are trying to discover is a guessable password and not a randomly generated key.