@leon99 We run a Preorder app full time, so I can share some context here.
It seems like the app is not making use of “Purchase options” - a new, native way for preorder apps to integrate with Shopify and share the right information about a product’s purchase. This is likely why you are seeing a note on the order and why it stays unfulfilled.
In general when you use a preorder app with purchase options under the hood, the order will flow into Shopify - just like any other order - but in other more preorder-friendly states like Scheduled or On Hold (a manual lock that needs to be overridden to start fulfillment). You’d then release the hold on a specific date or based on certain changes like when the product is restocked.
It sounds like what you’re looking for is something like this: Customer places order > Order stays on hold until stock is available > Product is restocked > Warehouse system is notified to fulfill. With an app that uses purchase options and a set of custom Shopify Flow actions, this should be doable. 
Hit me up if you need help with this!