So this is actually a lot simpler to fix than it would seem. I was tearing my hair out with this when I moved some assets to another folder and it would recreate them and then add empty references to the old folders.
The trick is you delete the old version one by one and use the “Replace References” option and replace the reference with the moved/new assets self. This forces the redirects to correct themselves.