One of the easiest ways to shut down someone relying on Warehouses is to play Militia (or any other handsize-lowering attack like Goons or Torturer).  Militia punishes every card that depends on a large hand size (Vault, Forge, Bank), but most of all an opponent that depends on Warehouse’s draw-and-discard ability to get through his deck.  Warehouses are increasingly ineffective as your hand size decreases, and after Militia, are often more of a liability than a benefit.  Drawing 3 Golds just to discard them is like playing Rabble on yourself.

Similarly, Militia hurts Haven quite a bit.  Playing Militia’d Havens is essentially equivalent to playing a less-effective Tactician, since you’d be cannibalizing your current hand.  And Militia is most devastating against Cellar (which basically becomes useless when Militia’d), but no one really builds decks around Cellar.