Is there a chance your rim diameter changed?
It would be reasonable for the original rim to be a 630mm because that was the style of the time, and for the newer rim to be a 622mm.
That results in the rim being 4mm smaller on each side, so the brake pad has to move down that far to be on the brake-track.
This alters the ratio of leverage giving less mechanical advantage overall.
One solution is to change to longer-reach modern dual pivot calipers, or to try and "drop" the entire caliper down with some kind of drop-bolt or mounting plate.
New caliper costs a fair amount, but brakes are not somewhere you want to skimp. Whereas a drop mounting can be a bit sketchy.
Example of both a modern caliper and still needed a drop plate, and yet the brake pads are still close to bottom of adjustment slot.
