Hi, as an inspector and as a level III I have run into this quite a bit. Customers always want a work-around to the paint issue. Obviously, you knew the requirements of 6.26.3, so why would you even ask the inspector to UT through paint? Either you can meet fully the requirements of the code or you can't. Not trying to be abrasive, but it seems the requirement was clear to you from the beginning, you were aware of it, so.... provisions should have been made. A UT inspection performed through paint is not a valid inspection, period, if you are claiming to have performed UT IAW D1.1.
The flaw in your argument is where you state "search with the angle beam and as long as there are no indications then leave the paint intact". Well, if the paint is intact, you are not finding everything you would if there were no paint, so right off the bat, you cannot guarantee you're finding every relevant indication. It's the "search", that is the important part. Depending on the paint, the attenuation at the interface could be very significant, or it could be nil. However, unless you can guarantee consistent paint thickness at every weld, which is unlikely, your results may vary. This is one reason, among others, that throughout many revisions of the D1.1, this requirement has remained.
Painting the cal block is a suggestion I hear often, from people who are, well, let's just say UT is not their specialty. This is not the answer either. You may get the EOR to buy off on through paint inspections, IF you can demonstrate, by properly qualifying a procedure, through probability of detection analysis, performed on a painted mock up of typical welds you will encounter, that you can achieve similar results as an inspection on an unpainted surface. However finding a level III to do this may prove problematic.
As an aside, it is not the job of, nor should it be expected, that the level II make this determination. His/Her job is to follow the qualified procedure provided him/her by the level III. If circumstances do not allow for this, then he shouldnt be expected to sign his name to a report where an improvised and unproven procedure, especially on a structural project, has been utilized.
There's my 2 cents, good luck to you.