Interactions in aqueous media between uniformly charged surfaces are well understood, but most real surfaces are heterogeneous and disordered. Here we show that two such heterogeneous surfaces covered with random charge domains experience a long-range attraction across water that is orders of magnitude stronger than van der Waals forces, even in the complete absence of any charge correlations between the opposing surfaces. We demonstrate that such strong attraction may arise generally, even for overall neutral surfaces, from the inherent interaction asymmetry between equally and between oppositely charged domains.