In short ...... O2 over 40% becomes a potential dangerous gas to work with. O2 is a very flammable gas and under pressure it can and will ignite when in contact with contaminants .
O2 clean means that the equipment is free of any dirt, grease or any other particles that could cause the gas to ignite. I would not be too concerned as the max EANx you are allowed to use in recreational Nitrox will not exceed 40%. This is something you should have been educated on in your Nitrox certification.
That's a little too short.
1. O2 is, obviously, an oxidizer and it will cause most materials to burn given a high enough partial pressure and a high enough ignition temperature. But it is a bit much to suggest it will spontaneously combust in contact with "contaminants". That is only going to happen if the ambient temperature is over the ignition temp of that particular "contaminant" when exposed to a high enough percentage of O2 under sufficient pressure. You still need an ignition source.
2. Many people will argue that anything over 23% requires O2 cleaning and that is not incorrect depending on what you expect the item to come in contact with. On the other hand, many shops have been doing banked fills of 36% to 3000-3500 psi for years with no ill effects. 3500 psi is 246 atmospheres absolute, and the PPO2 of 32% is 78.72. For plain old air it is still 51.66.
In contrast a partial pressure fill of 665 psi of 100% O2 needed to get a 36% fill in a 3500 psi tank will have a PPO2 of only 46.23.
What that means in the real world is that unless you coat you tank with 10W-40 motor oil, it is probably clean enough already.
3. O2 compatible gasses have a lower level of contaminants, and most specifically lower levels of hydrocarbons. The key here is lower levels not zero levels. So even if you perfectly clean the tank in a NASA clean room it gets a bit less clean on the very first fill with "O2 clean" gasses and it gets less clean with each successive fill. This is where the argument presented in number 1 and 2 saves everone's bacon. As noted above, regular Grade E air may potentially have higher levels of hydrocarbons, but its a difference in degree and one that has not been problematic in service on gasses with O2 contents under 40%.
4. Scuba valves are not designed for O2 service. They have flow paths that often have sharp bends, the valves often have sead spaces where moving gasses may come to a sudden stop and or be rapidly compressed and all of the above can generate heat. If you are not careful it can generate enough heat to cause ignition of any contaminants in the valve.
So, I think there is a great deal of need to keep your valves as clean as possible, but I see very little need to worry excessively about the tank itself.
That said, cleaning a tank is quick and easy. For my steel tanks, I'll give them a quick tumble to remove any flash rust, clean the threads carefully, tumble them some more with a cleaning agent (Blue-Gold or Simple Green Crystal) then thoroughly rinse and quickly dry them to avoid any flash rust. The whole process takes less than a half hour start to finish and you can do several tanks in an assembly line process with a tank at each stage of the process.
Cleaning the valve itself takes as much time as the tank, but it is 100% work rather than mostly waiting for the tank to tumble or dry. The irony here is that I suspect some shops do a pretty good job cleaning the tank, but more or less ignore the valve.
What bothers me even more is that many shops charge the customer through the nose for this process and the cost gets prohibitive if the customer has multiple tanks.
Now, that all relates to the OPs original question in this way:
It's absolutely correct that an O2 clean sticker means nothing once the tank leaves the building. Ideally, most shops have "air" that meets O2 compatible standards so an air fill is no big deal. If a shop's air does not meet that standard, they should refuse to fill a tank with an O2 clean VIP sticker on it (I think the nitrox bumper stickers are a complete and total waste of time and mean less than nothing). Theoretically, if you need the gas, then they need to remove the sticker, VIP the tank and place their own VIP sticker on it and they need to let you know that up front. But in the real world that does not happen.
It gets more complicated as some shops may stick blend with a compressor and filter system that does not produce comprssed air that meets O2 compatible standards (but hopefully grade E stnadards). In that case you are getting a nitrox fill, but may not realize you are again un-doing the O2 clean status of the tank and they probbaly won't tell you that.
So...the shop insisting on O2 cleaning as they partial pressure blend, needs to get with the program understand the flaws in that system. Unless they are the only shop supplying gas for miles around, or unless all the other shops in the area have O2 clean gasses, they are going to have cross contamination issues and the sticker really means nothing.
Where your liability may come into play is when they ask you if you have had the tank filled anywhere else other than their shop. If you lie and something happens, you could be liable. From their persepctive however, they need to assume you are lying and fill very carefully with very slow fill rates to avoid potential ignition sources on the assumption that the tank is not perfeclty O2 clean. Again this is where numbers 1 and 2 above tend to prevent accidents even with 100% O2.
