One of their leads appears to be made from stainless steel (at least the part that immediately protrudes from the battery, after that a piece of tinned copper is spot welded).
Partly due to my lack of awareness to the material and partly because of the severe limitation in space available, I shortened the leads which has left me with only the steel part that just refuses to accept the solder and I don't have a spot welder to weld something back on.
A colleague of mine mentioned a special flux that makes stainless steel to copper soldering possible but he has long ran out of it and can't remember the name or brand.
There are many results on ebay for "stainless steel flux" but I have no idea what would work and how well. Does anybody have any experience with this sort of work or any other suggestion on how to solder it?
and while the tabs look like they are made from stainless, they are not. I have found that they solder but need a bit of flux paste (in addition to the flux in the solder) and a fair bit of heat to make it flow. I assume that your batteries come from the same manufacturer as mine.
Be careful with the heat though as you can damage the battery. It may be worth clamping the leads close to the battery body with heamostats when you solder them to stop the heat running up into lithium and maybe starting a thermal runaway.
I wouldn't think stainless steel would be used in a battery. You might try a high heat soldering iron and some acid flux solder on the battery pad. You need high heat to quickly heat the pad area to melt the solder to prevent heat damaging the battery. I've found acid core/flux solder to be easier to quickly solder to battery terminals than rosin flux (no real electronics to impact). You might experiment with old dry cell batteries first. Below is possible info on stainless steel solder flux.
The tabs are aluminum and an aluminum flux should be used. I've also read that you can wet the tab with mineral oil to prevent reoxidation as you're soldering but I've never tried that myself.
Once and for all: The electrodes on a Lithium-polymer cell is Aluminum on the Anode, and Nickel plated copper on the Cathode, so stop talking about that stainless steel rubbish.
You will have a hard time soldering to that aluminum tab, without hurting the cell thermally while doing it.
You'll have a hard time soldering to the aluminum, even if you don't care about hurting the cell...
That's why they gave you a tab spotwelded on - typically when you see that sort of thing, where there's a solderable terminal attached to the device by spot-weld or crimp, it's there because there's a reason you can't solder to the wire it's crimped/spotwelded onto. Either it's something that solder doesn't wet, or it's near something too heat sensitive to solder to (in your case, both are true).