If by failure you mean the internals have packed up and are clogging the exhaust flow, you'd almost certainly notice the difference, at least at WOT.

What brand of O2 sensor did you use as replacement? I've read nothing but bad about the Bosch ones. NTK or Denso would be my first choices, followed by NGK.