I also buy parts from Rockauto but, that really doesn't clarify the correct sensor issue. Assuming they are okay and working fine as intended, you may solve the issue by replacing the spark plugs. These cars are 15 years old and even without a lot of mileage it may be best to change plugs and wires. Also if a non sensor safe RTV was used to seal something in the past like a leaking valve cover it could effect the oxygen sensor. I hope you have the car in an independent owned garage that specializes in european/mercedes vehicles. They will have the proper scan tool to dig deep into the Mercedes engine codes. Good Luck!