The dealer can technically review service records to see if the ECM has ever been reprogrammed, and if not, pull up the current ECM part # by looking up the VIN.
This TSB says to replace the O2 sensor and reprogram the ECM if the current part number is 23710-5W510. I'm not sure if the dealer will reprogram the ECM if you performed the O2 sensor replacement yourself, however, since the TSB calls for replacing the O2 sensor.
There is a similar TSB for my 2001 Pathfinder that involves reprogramming the ECM after O2 sensor replacement; however, I spoke with my local dealer's service adviser after I replaced my driver's side post-cat sensor to cure P0158 and he said that if the code didn't reappear within 100 miles or so of driving with a new sensor, reprogramming isn't required. Since yours came back on, reprogramming is indeed required for your vehicle.
Since your service adviser claims the $200 fee is "just" to determine the current ECM part #, print out the TSB I linked and the first sentence of my post and see if they can do that to determine your current ECM part # that way.
Welcome to NICOclub!