Then simply look through all non-deleted documents and see which files are still referenced and which ones are orphans. Delete the orphans. Done.
They can, it just would break those old links. A dumb decision ages ago doesn't force you to stick to it as you seem to imply.