Another method is a little more time consuming and expensive, but worth considering. You can rent a very high definition camera and macrobel (sometimes called rapid-rail) system. Mamiya makes one in the 80MP range, which may be high for what you are doing, but certainly better than the scanner method. You will certainly get more detail depending on the quality of the originals. Negatives do degrade over time, so you should check them out before going crazy. Even a 16MP camera is great, but there are many, many macrobel systems you could use if you have a good camera supply center nearby.
The macrobel system is much slower, because each negative is framed individually before photographing. But, depending on how valuable you consider the images. . .
Nothing beats the convenience of scanner and Photoshop.