Linking and transcoding, vs importing are different workflows, who ever told you you could link, then transcode, then delete, then batch import was wrong.
If you want to link and transcode, i always suggest you keep a copy of the original links on hand for the uprez portion of the project, that way you don’t have to go through the step of relinking the original clips.
In the end you would probably find transcoding (or retranscoding if you deleted the media) to be faster than a batch import any) You can even do the transcoding in the background while you work on other things.
Either way you need to have access to the original files to get the media back online, so does it really matter that you had to transcode rather than batch import?
As for Songster, as it is a third party app, you may be asking in the wrong forum. Have you tried pointing the re-import tool to the proper location? With Avid Batch import, its a pretty simple process to select everything and point it to the location of one of the files. I’m pretty sure Avid will usually find all the files in that location.
Glenn