Per my experience, capacitance measurements don't correlate with leakage. And as I mentioned, there were a number of leaky tantalums also. It IS a lot of work, but not much money and my problems went away. Start with the computer(and display)-related cards and see if the flaky readings go away - then on to the tape-handling related cards. Note that there are electrolytics in places other than on the incoming supply lines.
FWIW; I don't have any problems replacing tantalums with "modern" electrolytics - they are very good. Believe that tantalums were used in a number of places because they were physically smaller and space was at a premium. Todays electrolytics are half the size that they "used to be" and fit very nicely.
Charles