His VIP stickers don't claim to be in 100% O2 service so I don't see the problemThe problem is that there are two levels within the industry - air service and O2 service. Some dive shops are trying to carve out a third without any standard using anecdotal evidence. A VIP sticker that says acceptable 21%-40% is really meaningless because there is no standard behind it. Your shop may clean to near O2 service standards but another shop may not. Thus the problem.
(at least I don't think they do, I've lost track of the OPs tanks & valves)
As far as I know there is no official standard for 22 to 40% service at all. Its half CYA for cylinders that are basically clean (i.e. the new Fabers cited, new valves from DGX) but the manufacturer/distributor doesn't want to have the liability for O2 service. In other cases its just an excuse for a shop to charge more to wave a black light around and pop in a Viton O-ring. Its not like even a scrupulously clean scuba valve is even actually suitable for O2 service in the first place, the design is all wrong (fast opening with a nylon seat and a whole bunch of sharp turns)
For the OP I would either:
have the valve cleaned to the same level as the VIP sticker
get new VIP stickers so the tanks are in air service
Who knows how gross used valves are inside and if the burst disk is ancient etc. So I would tend towards having everything cleaned and not being cheap.