A number of studies have identified a tendency for exhaust gas recirculation (EGR) coolers to foul to a steady-state level and subsequently not degrade further. One possible explanation for this behavior is that the shear force imposed by the gas velocity increases as the deposit thickens. If the shear force reaches a critical level, it achieves a removal of the deposit material that can balance the rate of deposition of new material, creating a stabilized condition. This study reports efforts to observe removal of deposit material in-situ during fouling studies as well as an ex-situ removal through the use of controlled air flows. The critical gas velocity and shear stress necessary to cause removal of deposit material is identified and reported. In-situ observations failed to show convincing evidence of a removal of deposit material. The results show that removal of deposit material requires a relatively high velocity of 40 m/s or higher to cause removal. The resulting shear stress within the deposit is 0.03 to 0.045 kPa. The high velocity needed also results in a high pressure drop across the cooler which makes removal using a purely shear-based difficult in practical engine systems. High flow rate cases in the in-situ experiments did not show evidence of removal even though the velocities were estimated to be high enough; this finding suggests that material removal is not the dominant phenomenon that leads to stabilization. Rather, a combination of shear forces and reduced attractive forces between incident particles and the deposit surface is proposed that results in a lower adherence of incident particles to the deposit, limiting its growth.