I use SPD's, do about 5000 miles/year, and it took me over a year to wear the right one down to the point it was slipping out.
(I usually unclip just the right foot at stops.)