Nope, you've nailed it, you need an embedded microservice - thankfully that is exactly what Node.js is good at and Node-RED has everything at hand.
While you don't have to use a module, it most probably makes sense.
You want to avoid a database if you possibly can because it adds overheads that you probably don't need. You shouldn't need one here, you can keep the references in memory using JSON structures. You will have to rebuild the schedule on a restart anyway. Using JSON has added benefits since, if you do it right, you can allow overrides and/or schedule replacements to be sent via an inbound msg.
I've started discussing how to build a full-featured scheduler with @Andrei in a private chat. I'll see if I can add you to that chat if you are interested. I've laid out some design ideas and suggested the same approach as you've done - start with a stand-alone microservice to test out the ideas before we start on the actual node.
I wanted to do this outside the general forum simply so that we could agree on a basic approach without too much chatter but if anyone is interested in collaborating, I'm sure Andrei wouldn't mind, I certainly don't.
So I'd suggest using this thread to continue the general sharing of ideas and thoughts and the private chat to begin exploring possible solutions until we are ready to share more widely. Of course, I'm not suggesting that other people might not want to persue their own ideas - I will say this, the basic design idea that I've set out so far is fairly complex in order to achieve a powerful, flexible, general-purpose scheduler for Node-RED. Undoubtedly there is still room for other approaches as well.
@scotie, let me know if you would like adding to the private thread, I think I can do that.