I would use CRC MAF Cleaner spray. It can be found at WalMart (I'm fairly sure), Advance Auto, etc. The bottom of
this article has instructions.
It may not be absolutely necessary to have your ECM reprogrammed to accommodate the new rear O2 sensors - it could simply be possible that both are faulty. You should be able to ask for a complete service history printout from your local Infiniti dealer's service adviser. I'm not sure whether you can get any work reimbursed if they didn't follow a TSB when they should have. I'd need to see what work was performed to see whether it's viable to call Nissan/Infiniti's customer service line and complain.
Yes, Advance Auto, Harbor Freight, etc should have a 22mm (7/8" will also work) oxygen sensor socket.