In 1996 while we were in Mobile after coming down the river from Chicago, we were in a boatyard for a few weeks. We had same stuff on our deck from boats being sanded. The deck was covered. I remember using Muriatic Acid to get it off, but don't remember if I mixed it or used in straight. You might try it on a small area and see how it works for you, and be careful and read the label...it is strong stuff.
Good suggestion but be careful around portholes and deckhands as power washer can remove the caulking if too much pressure applied. I have also had good success with StarBrite deck cleaner. Expensive but can be cut with water and the chelating agents minimize the scrubbing if you follow directions.
Great for scuff marks and dirt spots on flat surfaces, but a whole deck of non-skid ?