a lot of it depends on how you approach the new dealer. If you go in there saying "hey i was just at _______ and they claim an upgraded power wire on my battery from the previous owner is causing my 02 sensor to go bad, which we all know is complete BS. I've heard nothing but great things about the service department here, so i figured i'd drive the extra distance and see if it's all true."
Right then and there the service writer(most likely who you will be talking to when you get to the dealer) will almost feel obligated to look past the wire and have a technician find the cause. The reason your O2 keeps going out is because they are just replacing the part, not following the code. A CEL is not to tell you THIS PART IS BROKEN. It's supposed to aid you in your diagnostics to help find WHY it is broken. Clearly a poorly trained technician worked on the car, and the ONLY reason they refused to work on it the second time is because it would be a come-back, and neither the dealer nor the technician would make any money off of it, because they neglected to fix it right the first time. MAKE SURE when they send you your CSI(if they haven't already) you give the dealer a really bad review. You might think those CSI's they mail you are useless, but CSI's are the single biggest concern of not only the service department, but the sales department as well. If CSI scores are low, technician pay goes down, dealer rating goes down, AND the CSI score determines the dealerships inventory. Poor CSI means none of the specialty cars, and an overall poor inventory.
I just went through the same crap two days ago. My car just hit 18k miles, it's about 8 months old and i'm the original owner. I put some simota carbon fiber intake thing on it so i would not have to replace air filters, just clean them. Recently it started rattling at stop lights, which i figured it just came loose. But if i have the car in the sport mode and try to engine brake, the whole motor rocks. I took it to the dealer, came back 6 hours later when they called, and when i get there they say "your intake is restricting the engine's movement." Keep in mind i'm still wearing my Mercedes-Benz shirt. Their technician is trying to tell ME, another technician(and most likely more formally trained, but that's neither here nor there) that the intake is RESTRICTING my engines movement.
At this point i was just in shock that he would try to blow such smoke up my arse. I grabbed the intake, shook it back and forth, and said "so this rubber tube and carbon fiber box that's being held down on the STOCK rubber bushing by a 10mm bolt is restricting my entire engine from moving?" and he says "yes." I proceed with "then please explain to me why the engine is moving MORE than it should be." he got quiet and said "what you are feeling is completely normal." The last thing i said before leaving those idiots was "i thought it was being restricted, so that's normal? I guess i'm going to another dealer to find out what was WRONG with my car for the past 17k miles since obviously now it's normal. Thank you guys you just might be the best service department i've ever seen. I'm gonna stop by the front desk and pick up an application." Needless to say i will not be dealing with that dealership ever again.