The problem with stainless steel is that it has a thin oxide skin (Just like Aluminimum) and the solder does not adhere to this oxide.
There are fluxes specifically designed for use on stainless steel. These are usually quite agressive acids, that dissolve the oxide.
It also helps if you use sandpaper just before soldering, and do this under an protective atmosphere.
For example, fist use dry sand paper, then apply some "regular" flux just to form an air tight layer, and then scrub again with a glass fiber pencil through the flux.