The only information I've ever read on "stale air" was a passing mention noting that corrosion (which consumes oxygen) could decrease the oxygen fraction in the air. Obviously, I just had to try some numbers out...
Let's start with a fictional "Iron 80". Now, since we know that 1 mole of gas occupies 22.4 liters of volume at STP, and using the conversion 28.3 liters per cubic foot, we find out our ~200 bar I-80 is a conveniently-sized 100 mole tank. Since it's been there a while, we'll assume it was filled with standard air (since we would've certainly used a nitrox fill by now), and we'll simplify things by rounding to 21% O2 / 79% N2.
In NAUI's Nitrox Diver course materials, they state that the EAN dive tables can be used with gas mixtures within 1% of the stated fraction of O2, so we'll assume our old air will be good if it still has 20% oxygen by the time we use it. Doing the numbers, that means we can "use up" 1.25 moles of O2 to form 0.83 moles of rust (Fe2O3, the red, flaky rust), which is 133 grams, 0.29 pounds, or about 4 and 3/4 ounces of rust. (Incidentally, the I-80 would've lost only about 40psi from the oxygen used up to make the rust, assuming the rust was the same volume as the iron from which it came.)
So, basically, if you shake your tank and hear a big pile of rust rattling around inside it, don't use it, but stale air should likely be the least of your worries. I'd be more concerned about getting crud into my regulators.
) That's impressive info!! Are you a rocket (or scuba) scientist? That's some deep stuff! 
