@Rhylon > Chances are you have managed to somehow move the file / folder locations and rekordbox is not picking them up because the locations in the database don't match the physical file locations.
If you had playlists within rekordbox or iTunes, the XML itself was just a 3rd point, so your loss of that one is likely just a missing file, the other playlists would exist within rekordbox or iTunes.
The first step was probably the one that caused the most problems, the rest just repeated it. And it's likely that the changed file locations also affected the missing XML file.
Start by checking the file location within the rekordbox database vs. the actual physical file location - you can do this easily by showing the Location column within rekordbox and see if that path matches the file's actual location.