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.)