Kevin, this occurs quite commonly, especially when product is shipped overseas with freight sitting in containers over extended periods of time. At Ervin, we poly line all shipments, but rust is inevitable. As Walter mentioned above, it's best to cycle the media by blasting it against a target. Depending on the size of your machine and the quantity of shot it holds, you'll have to time it accordingly. Contact me if you need more details on how long this needs to be done for.
Rust is a surface phenomenon, and descaling it will not impact your arc height values. If the particle size gets reduced by impacts (which is the natural failure mode for any peening media), it will get eliminated by your airwash separator, cyclone or bottom screen in your classifier. 'Descaled' shot will also help with avoiding part discoloration.
For your information, AMS grade material goes through a conditioning process prior to shipment. In other words, there is no surface rust on the shot particle during shipment. Transit rust is what you're noticing on the product. We have a bulletin for proper shot storage as well that I am happy to email you if you wish.
We discussed this at a recent SAE meeting and none of us felt the need to make a statement about rust in the documents since it's subjective and a rather simple fix.
Hope this helps.