I can't understand why this is happening; I've never encountered anything like this.
Best I can say is to make sure you're using the latest version. I think the newest update changed the Spacial Disk menu; there's now an option to review the messages you get from your Starfarer whenever you beat a boss, including being able to receive any essences you, for whatever reason, don't already have or have gotten, so if you've already beaten Skeletron in a world, then the message and essence should be acquirable through these means. Try this out, let me know if it works or not. I'm curious.
Also, no, you can fight the bosses in any order. You could go from making a new world straight to Wall of Flesh, and there would be no issues.
But ultimately, what I say should be taken with a grain of salt. PaperLuigi is the one you want a response from the most, as they're the one who made the mod. I just thought I'd give my two cents on it.