I may be comparing apples to oranges here, but I had a '94 Probe with 130K on it that did the same thing. Turned out that it was the IAC motor, not the O2 sensor. Since Mazda parts are ludicrously priced, I traded it in for my 'tour, which pulls the same crap at 60K... on rare occasions, fortunately.
Black/tan early '98 Contour SE Sport; V6, MTX, loaded
Kenwood KDC 316S CD deck; aux. dome light mod; trunk popper spring; resonator bypass; hood strut mod; SVT grille; Continental tires
Mom also has black/tan '98 Mystique LS; V6, ATX, Alpine CD deck
| 
