Samarium Cobalt (SmCo) magnets can withstand high temperatures much better than Neodymium, but they are more expensive and more brittle. If you find that you are demagnetizing the Nd magnets, maybe give them a try.
Personally, I'm no soldering pro, but I've had good results soldering to Nd magnets. I sand off the shiny coating, stick them to an anvil (actually, it's a scrap of a train track), and use a 300 watt soldering gun to get the job done quickly. The hardest part is pulling the tip of the soldering gun away from the magnet. Those suckers are strong!
Also, I think the size of magnet is an important factor here. It seems to me, the bigger the magnet, the less likely you are to demagnetize it by heating up one surface. The magnets I have used are 0.375" DIA x 0.25" THK, which makes them much stronger than necessary for the job of holding a wire to a battery (in fact, it can be a little annoying to try to pry them apart). Good luck!