I had it with me this past summer out on the sea and the stainless steel held up just fine - no rust (can't say the same for my Leatherman Wave).
I'm less interested in the debate of what knives to get than what you mentioned here. I EDC the LM New Wave, and I'm curious just what sort of use yours saw with regard to salt-water induced rust. It sounds like you were actually using it on a boat. If it was continually drenched in salt-water, did you rinse it with fresh and oil it regularly? Any other maintenance or was it just left to it's own devices? I ask because I would like to avoid the same result. Also, what parts rusted and were you able to recondition it?