Have you tried sourcing the parts you need through a marine hardware store?
Although one problem with using stainless steel nut's and bolts is the fact that in some cases the nuts and bolts will gall up and seize together, then you have big problems, you should use some anti-seize compound on all stainless hardware to prevent this.
I use a product call "Evapo-Rust" you just put the part in a plastic pan with a cover and cover it up with the Evapo-Rust for a few days, the rust should be gone, you should wire brush the big stuff off first.
You can also use this stuff called "Corroseal" it converts the rust to magnetite then seals it up.
Corroseal Rust Converter/Primer is an industrial strength product for all your marine, household, automotive, and industrial rust problems.
www.roddapaint.com
Also you may just be dealing with surface rust, the part may still be useful, if treated with the products above you may get a few more years out of it.