blue claybar (any cheap variety) would have smoothly removed it) clay works by removing all loose bits that are above the surface of the paint (paint being the most %age of flat surface, the paint specks being the least - hence the clay will remove them, that is how it works).
I have removed a ton of stuck like a bad disease road debris from the front of my car with a claybar and baby shampoo. Pulls everything out, it will even pull out what scotch brite pads will leave behind on paint.
btw - with that sort of procedure your car's paint is now at 25% life only, I can bet the clear coat is gone or nearly gone, It would be best to apply some 3M glaze to the finish and apply a sealer too. Otherwise you might see the paint become cloudy - specially if you wash with regular detergent and water.