I think I paid $10-$15 extra when I swapped out my 20# CO2 tank the first time for the recertification. It was really old and rusty. I think the guy I bought it from had it sitting out in a barn or something for like 5+ years. They should just swap it out and charge the recertification fee. Most places don't actually refill your CO2. After your first one, this really doesn't matter, as long as you plan on using all your CO2 within 3 years or whatever, as you just swap them out, instead of refilling the same one.
Although, they may be talking about a welder's stamp, or something of that nature, which means that it belongs to a certain welder or whatever. If that is the case, then I think you would have to contact whoever it says owns it, and have them tell them it is okay, and that it is yours.
If they won't fill it because it is too old, just look around at other shops.