Although I am temporarily in Southern California, my permanent home is in Fredericksburg, and I have run into the same problem with some of the Northern Virginia shops. I believe that the information contained in this
link is what the shops are using to support the use of a new standard. We may all be used to the 40% rule, it would seem that some shops are adopting this new 23.5% rule. The article covers it in detail.
Since there are no SCUBA police the industry is covered by regulations and practices from many different and sometimes contradictory sources. Agencies like NASA, NOAA, U. S. NAVY, and the U S Compressed Gas Association, as well as the insurance industry create a confusing web of standards.
Personally the 40% rule has, in my opinion, proven itself over time. But then I don't own a SCUBA shop and I don't fill my own tanks very often, so my personal opinion doesn't count for squat. It seems that there are several shops in Northern Virginia that are adopting this newer 23.5% rule, other parts of the country may not have any shops that are adopting this standard. All I can suggest is that you get your tanks maintained to the standard that is used by the place you get fills.
It is unfortunate that the charges were a surprise to you, the shop should have been very clear when you took the tanks in.
Hope this information helps,
Mark Vlahos