I have been using 1800maH cells made by Gold Peak (I think). They are the semi-flat topped cells just like the original HP. You can find cells have a true flat top, others have a small raised button like a standard AA cell. These have a larger, shallower raised button. NiMH cells can be found in 1300 to 1800+ maH. Any capacity should work fine. The slow charge rates of the HP charge circuit are quite compatible with the NiMH cells.
Just about any battery store (Batteries Plus, Batteries, Etc, etc) can make up a pack by welding a strap across the bottom end of the cells (don't solder cells, it ruins the seal, etc).
I then fill in the valley on the top side with thickened epoxy. The bottom side gets about 1/3 filled in. This makes the pack keyed like the original so that it cannot be put in backwards.
When I install a pack in any Spice machine I first place a piece of ribbon in the battery compartment to use as an extraction aid... no more broken contacts trying to lever it out.