The first thing I would do is contact a provider representative, if you have one, and go over all of this with them, and find out why this is happening. Barring that, I would be sure to send in OP reports and IP notes with every claim for those types of services, so that they get the claim and the documentation all at once. That might prevent the lag between them receiving claims and requesting notes, and they can process the claims more quickly.
As for the pacemaker/generator issue, with the auths...do they want the authorization number on the claim? Do they want something in Box 19 on the claim? There is a disconnect here that you need to get to the bottom of. And yes, it is the principle of the matter, I agree. I am not sure if the provider is contracted with UHC or not, but everything needs to be argued/appealed, even if it means highlighting the treatment note to explicitly show where the service was rendered.