Sad to say, I've come to the same conclusion. The effort required to get the wax off without also ripping off the delicate solder tabs just wasn't worth it for me. Since the manufacturer is only about an hour's drive away from my home, I even contacted them to see if I could buy the seconds without them being encased in wax (I pick them up, any breakage on the way home is my problem, etc.) but it didn't work out.
I had followed the standard directions of putting the block into a pot, covering it with water and heating it on the stove. That worked well for getting the majority of the wax melted, but I ran into problems trying to separate the cells and lifting them out out of the near-boiling water one at a time without disturbing the solder tabs. Plus, of course, the melted wax floats so while I could skim off the majority, there was always a little bit of melted wax that would happily restick to a cell being lifted through the surface... If I was to ever try this again, I'd reject the near-boiling water approach. What I'd do is put the block in the stove, leads side up, elevated a bit so that the melting wax drops away from the block. Instead of trying to separate the cells while they are hot, I'd let the block cool off. At this point, the cells should still be stuck together which would hold the leads onto the cells tightly but the external part of the leads should be wax-free. I would then (gently!) straighten the leads as much as possible so they won't be tangled when the cells separate and then put the entire block, external leads pointing up again, into a solvent to dissolve the wax between the cells. I don't suggest that this would make the dewaxing easy, but I believe it would be easier than the near-boiling water technique.