lasse, remove the vices ..... and give them a really good scrubbing with a stiff wire brush .... and then wipe it all over with oil, especially the threads so that they "turn" easily.
After you get the rust off ..... you can polish the metal with "00" steel wool.