What you describe is very typical of painted aluminium cylinders.
Aluminium also forms rust, aluminium oxide AL
2O
3. This is not commonly called rust, but it is essentially the same as a piece of iron rusting, it oxidizes. Unlike iron oxide, aluminium oxide does not flake off the base material. It forms a protective layer on top of the aluminium underneath which is just 4nm thick. The underlying aluminium does not come in contact with oxygen anymore. Therefore, it cannot form any additional aluminium oxide. Aluminium is protected by a layer of rust from rusting. This forming of a protective layer is also called making the metal passive. Passive in the sense that the underlying material will not react with oxygen anymore. This principle is at work in stainless steels, where more than 11% of the alloy's composition is made up of chromium atoms. These chromium atoms shield the underlying iron atoms from further oxidization by creating a thin layer of chromium oxide (Cr
2O
3). Again, it is only the outermost layer of the base material which comes into contact with the oxygen. Making a metal passive, can be achieved by several different methods. Painting a metal surface sufficiently is also a form of passivating the material. It prevents the base alloy coming into contact with the oxygen from the surroundings. All of the different methods have in common that they put a barrier between the base alloy and environment.
The oxygen atoms essentially bounce off the layer of AL
2O
3. They cannot react with the base alloy to create more AL
2O
3.
Unfortunately, these protective layers only work if they are sound and in place. Scratching the paint of a piece of iron will of course lead very rapidly to rust. The same is true if the formation of the passive layer is inhibited. A tight-fitting boot on an aluminium cylinder will inhibit the formation of this layer, so do the rather shoddy paint jobs. The aluminium oxide can't stick to the base alloy, leading to more and aluminium oxide formation. A tight-fitting cylinder net on an aluminium cylinder does the same. An aluminium cylinder is always left best without a net and without a boot and without any paint. The paint can chip and let oxygen and water get to the base alloy, while inhibiting the formation of a protective layer of aluminium oxide. The result will be a slow buildup of powdery aluminium oxide underneath the paint. This leads to the formation of small "bubbles" underneath the paint and the eventual chipping off of that very same paint.
A tight fitting boot, net or shoddy paint all inhibit the formation of the passivation layer.
Long story short, get unpainted cylinders or just strip yours.