Stainless deck nails are rusting

The driver on the nail gun is hardened steel. It leaves a really thin layer or spot of steel on the head of the nail which starts the rust which will continue to spread over time in a salt air climate.
Brushing has to be with a brass wire brush [affil links] or a flap wheel or a wheel of stuff like scotchbrite or it will actually cause more rust. Try using naval jelly [on eBay or Amazon] , or a rust converter [on eBay or Amazon] product, let it dry and then paint.

If the deck is on the Gulf, there's probably a lot of chloride in the atmosphere. Most grades of stainless will corrode in chloride environments. Try something powder coated (and don't use the cheap stuff).

According to the American Wood Council, suitable fastener materials for pressure-treated wood in coastal areas are 304 ('18-8') and 316 stainless. Since you've already experienced stainless corrosion, use the better, 316 grade.

The newer wood preservatives are more corrosive toward metal than the banned CCA (Chromated Copper Arsenate). For more information: Go to www.awc.org, search for Corrosion, click on the 1st result "American Wood Council Mold and Moisture in Homes."

All stainless steels will oxidize given time and a high moisture environment. The nails are most likely stainless, but of the wrong grade for your purpose, take a magnet to them and see if it sticks, if it does (most likely) you have stainless nails that are high in steel and low in chrome. I would suggest bronze or brass nails for this application as they will have surface oxidation, but will no corrode beyond the surface.

Some stainless alloys resist rust better than others, the alloy is fairly important - the first suggestion would be to try an alloy that is more corrosion resistant. I would make more direct suggestions, but I don't really deal much with stainless - use the search engine on this site and you should be able to find some information that can help.

The second suggestion is to make sure that the nails have been passivated - this builds up an oxide layer on the part and provides most of the corrosion resistance. Incidentally, this layer can be compromised by sever sanding and other working, so try not to sand the head of the new nails if you can help it.

A third suggestion, the stainless steel is corrosion resistant, but the wire wheel you used probably wasn't and could have easily embedded free iron into the head of the nails - this iron, then, would be susceptible to rust.

More than that I can't offer - as I said, stainless steel isn't really my thing. But, use the search engine, the archived letters contain a wealth of information that is fairly easily overlooked by new users.

Good luck!