This work explores the impact of nanoscale surface heterogeneity, small relative to the effective contact area between two surfaces, on pairwise colloid-scale interactions. Polycation-based positive patches, of order 10 nm in diameter, arranged randomly and lying flat on otherwise negative substrates, were used to create surfaces whose competing attractive and repulsive features determined the net interactions with opposing surfaces. Lab experiments and simulations of the adhesion of gently flowing dilute negative microparticles varied particle size (0.5-2 mu m), ionic strength (kappa(-1) = 1-12 nm) and the density of heterogeneity on the collectors. Limiting behaviors from heterogeneity-controlled at high ionic strength to mean-field-like interactions at low ionic strength are reported. When heterogeneities are important, pairwise interactions are more attractive than predicted by average surface properties (e.g. per DLVO), and an adhesion threshold, describing the minimum average density of cationic features needed for single particle capture (adhesion), depends strongly on Debye length. In the opposite limit, the threshold becomes insensitive to the Debye length, and the average surface character approximates the interactions. An analytical treatment, reduced to a simple scaling argument predicts a -1/2 power-law dependence of the adhesion threshold on Debye length and particle size. A slightly stronger particle size dependence in experiments and simulations results from hydrodynamic contributions along with slight scaling differences in electrostatic, van der Waals, and hydrodynamic forces. An analogy to biological ligands is made for the heterogeneity-dominated limit: it is discovered, for this particular system, that engagement of as few as 20-100 cationic patches dictates particle adhesion (with details depending on flow, particle size, and ionic strength), similar to reports for selectin-mediated rolling of white blood cells during the inflammatory pathway. Also discovered is a heterogeneity-dependent crossover in the effect of ionic strength on particle capture, where added salt promotes particle adhesion in most cases but stabilizes the particles when the heterogeneity becomes relatively dense. (C) 2009 Elsevier Inc. All rights reserved.