Sadly, there is no way to recover them.
Here's what happens. When a ni-cad battery is charged, it grows crystals between foil sheets. When you dischage it, the crystals shrink. But. They don't all go back to the same size. Some stay just a tiny bit larger. Once this starts, it's the beginning of the end. Like a stalactite, the crystals grow in layers. And only one layer (the outer) can discharge. This is why you're told to not recharge batteries until they're totally dead. Make sense now?
When these ovesized crystals grow big enough, they pierce the foil conductors and bleed into the next layer, thereby killing both their own and the next layer, reducing the battery's power. That's probably where you're at now.
Batteries can be reconditionned if they're caught before they pierce the foil. Not to 100%, but better. You need a battery butler. It's a simple electronic built, if you've a little talent in that direction. And the plans should be findable on the net. My copy went MIA about 20 years back.
As for new (replacement) batteries, try Duracell instead of IBM. I always got my batteries direct and saved a chunk of change.