I use the green Scots-brite pads. For me they have just the right abrasion qualities to take off the crud and give a nice finish.
The banacles will need a scrape with a Homebase stainless steel scraper
I haven't tried this yet to varify it but I heard that household de-scaler, the stuff used to remove lime is good.
Normally, I use 400 grit wet and dry paper and this works well. It is tough cutting through the limescale / shell lining you get, hence next year, I will try the de-scaler first to soften the stuff!
I use Starbrite hull cleaner - it has dilute Hydrochloric (I think) acid in it, and that takes everything off a treat. I then use very fine sandpaper to expose a new surface, otherwise the prop has a slight tendency to rust. (I can't remember the rationale for this, but there is some science behind it somewhere /forums/images/graemlins/smile.gif).
Hydrochloric acid removes the chromium oxide layer on the surface which is what prevents stainless steel rusting - hence the rust you've seen. By abrading the surface afterwards, you expose a fresh surface which oxidises immediately.
An alternative is sulphamic acid (Carlton's kettle descaler) which takes longer but doesn't destroy the oxide layer.