Did some more calculations just for the fun of it. It looks like you'd need nearly 16 exabytes of storage to hold the MD5 table for every 9-character hash [1]. Not accounting for any database overhead. In high density, you can fit a petabyte in what now a days? Half a rack? So around 8,500 racks. Certainly in the realm of possibility for a government but it would be a lot for storing just one type of hash list.
I feel like there should be a more efficient way to store these things. You have a complete enumeration of possible inputs (passwords), but unfortunately we need to go in the opposite direction, so we couldn't just index into a n*9 bytes array. Depending on how well distributed the md5 hash space is, it's possible a prefix tree might save you a bit of storage (you'd only have to save a couple of bytes per entry to cancel out the overhead) but I couldn't tell you the numbers there. Otherwise I think you're right, and we'd just have to store a map of md5 -> password.
(Edit: Also being limited to alphanumeric for hashes and printable ascii for input gives you pretty good compression potential.)
[1] https://www.wolframalpha.com/input/?i=%28630249409724609375+...