For some stupid reason, Varta reused the same model numbers for NiCd and NiMH batteries in the Mempac line. Older versions were NiCd, newer ones are NiMH. I have catalogs from 1988 that are NiCd. I don't know when the changeover took place.
NiCd memory backup batteries were typically trickle-charged. NiMH batteries are less tolerant of trickle-charging and require a lower charging rate. Newer NiMH batteries have improved their tolerance for trickle-charging.
If the guy who had the leads melt off is the one who used Duracell NiMH AAA batteries, they would have handled the NiCd trickle-charge current with no trouble. Maybe he had another fault that caused overcharging rather than trickle-charging. You could try something like he did. Try a NiMH battery, but don't solder it into the board. Find a spot to put it and buy a battery that fits that spot. Run wires back to the original location. Wrap the battery to protect the board from any leaks.
Bottom line here is that NiCd is a dying technology. You can find them on ebay or aliexpress, but there's no way to tell what the quality will be. I have a couple of systems that used about 20 NiCd D cells for battery backup. One I just removed the old batteries and moved on. For the other, I'm considering a LiFePO4 retrofit, but that requires a complete redesign of the power supply and the addition of new charging and BMS circuitry.
Ed