The oxide coating is about 115/1,000,000cm thick. It's gone if you scratch the metal with your fingernail.
Oxygen starvation corrosion is a real problem. But it requires both the exclusion of oxygen, and a corrosive environment. The damage is typically only found when a part is soaked in sea water (chlorides are the biggest offenders) then somehow the oxygen is eliminated from the metal's surface. Example, a stainless shaft in a cutlass, the boat is stored, and in a few months the shaft will have a rough spot where the shaft rested in the bearing. Or a metal part with a rubber grommet or bushing-sea water gets under the rubber, and the NaCl damages the stainless. It's not something that happens when something is just fastened with SS in a dry environment, then sealed by epoxy; the damage requires that corrosive element before you have a problem. The more noble grades of stainless are less prone to crevice corrosion, but become cost prohibitive.
It's called stain-less steel, not stain-proof. In the end, buying bronze fasteners from Glen-l is not going to cost significantly more than those nasty bugle head deck screws you are looking at in home cheapo... not to mention those nasty bugle heads are made to "self countersink" themselves in treated lumber, not provide maximum holding power with minimum wood damage.
http://www.alberg30.org/maintenance/Ste ... Corrosion/ for a great image of a nearly dissolved fastener.
A machinist friend of mine will argue for hours about how it doesn't happen, but he is the sort that will try to prove the earth is flat because he can't see the curvature from his deer stand.