For MD5, a core problem is that the total number of computable hashes is small, meaning that 1) rainbow tables are possible because the entire hash space can be stored in memory on commodity hardware, and 2) specific collisions can be trivially engineered.
This means that both data authenticated by MD5 hashes (say, software package signatures) and access mediated by hashes (say: passwords, if you're incredibly stupid), can be trivially hacked.
I've taken the opportunity to look up how rainbow tables are used, and in practice, what are constructed are rainbows of likely hits, as well as exploitation of crytographic weaknesses in the MD5 algorithm. So, no, it's not the total address space, but, say, for keywords in multiple languages or known revealed passwords (of which the most common give you tremendous amounts of access -- the top 10 and 100 passwords will access many systems, and lists of millions are now available, for which rainbow tables are easily constructed). And the collision problem also remains.
As for assembling large amounts of storage: with distributed systems, whether on bare metal, cloud systems, or botnets, it's possible to aggregate terrebytes of memory (not merely on-disk storage) for quite modest budgets within reach of a company or moderate-high-net-worth evil genious, let alone a state actor. For commodity x86 servers, high-end memory now looks to be ~320 - 512 GB, though terrabyte range wouldn't surprise me (I think SGI are still pushing the envelope in this area in their Rackable incarnation).
This means that both data authenticated by MD5 hashes (say, software package signatures) and access mediated by hashes (say: passwords, if you're incredibly stupid), can be trivially hacked.