If was a grey stain that was removed by applying acid then it was most likely "dirty" calcium/mineral scale. Calcium carbonate is white naturally but when it precipitates from water it will pick up any suspended solids and form an off-white to dark grey color. Being in Yuma, you are also in the "Winter Vegetable Capital of the World" which means lots of farms and tons of atmospheric dust. You also will have very hard water like anywhere else in Southern AZ. Also, many people in Arizona make the mistake of using calcium hypochlorite to chlorinate pools and will often "sprinkle" that around a pools edge as well as add liquid chlorine and other chlorinating granules (dichlor) by that method. Pool techs are not know to be mindful in how they add chemicals. So often a large amount of chlorine and, possibly calcium, winds up at the bottom edge of the pool. This can cause a spike in pH and calcium hardness leading to scale and staining. Your description sounds very much like that.
Your options are to either control your CH carefully by using softened water (my pool's autofill is hooked up to our whole house water softener) or to control CH by periodically draining and refilling your pool. If you are using chlorine in your pool, it should come primarily from liquid chlorine, not solid sources.
As for products to control scale, you can use any HEDP based phosphonate scale inhibitor but it's not a one-time deal. You will add a startup dose and then regular maintenance dosing to keep the scale preventer at the appropriate concentration. It will be an ongoing cost and several of the best scale preventers cost upwards of $40/gallon. You will be using gallons of the stuff every month. Scale inhibitors will cause your phosphate levels to rise. Phosphates are algae nutrients and so as the phosphate levels rise, so will the risk of algae and you will need to keep tight control of your FC/CYA ratio to ensure that you don't dip below the minimum. Otherwise, algae can get a foothold and then you'll be SLAM'ing a pool which is no easy task when the CYA is up near 90ppm.