This work investigated how particle softness can influence the initial adhesive capture of submicrometer colloidal particles from flow onto collecting surfaces. The study focused on the case dominated by potential attractions at the particle periphery (rather than, for instance, steric stabilization, requiring entropically costly deformations to access shorter-range van der Waals attractions.) The particles, "spherical polyelectrolyte brushes" with diameters in the range of 150-200 nm depending on the ionic strength, consisted of a polystyrene core and a corona of grafted poly(acrylic acid) chains, producing a relatively thick (20-40 nm) negative brushy layer. The adhesion of these particles was studied on electrostatically heterogeneous collecting surfaces: negatively charged substrates carrying flat polycationic patches made by irreversibly adsorbing the poly-L-lysine (PLL) polyelectrolyte. Variation in the amount of adsorbed PLL changed the net collector charge from completely negatively charged (repulsive) to positively charged (attractive). Adjustments in ionic strength varied the range of the electrostatic interactions. Comparing capture kinetics of soft brushy particles to those of similarly sized and similarly charged silica particles revealed nearly identical particle capture kinetics over the full range of collecting surface compositions at high ionic strengths. Even though the brushy particles contained an average of 5 vol % PAA in the brushy shell, with the rest being water under these conditions, their capture was indistinguishable from that of similarly charged rigid spheres. The brushy particles were, however, considerably less adherent at low ionic strengths where the brush was more extended, suggesting an influence of particle deformability or reduced interfacial charge. These findings, that the short time adhesion of brushy particles can resemble that of rigid particles, suggest that for bacteria and cell capture, modeling the cells as rigid particles can, in some instances, be a good approximation.