Files moving around is a little troublesome, folders even worse… still a vault difference comparison could be useful for cleaning up some of this mess.
Alternatively you’d need to use some git tool to go through every change back in time, and change to preserve the “correct” change along with modifications needed.
The only programmatically alternative I see is to loop through all non-existing links, and try to match up the leading part of all file names against that list. That could work, but it would require for all the links to have a full path to the note. Any notes with only partial matches would cause some issues.