I have a similar setup on a number of SaaS platforms I develop and manage. This type of setup is certainly desirable, as your clients suggest. You should plan to serve each customer site on its own domain, probably also with *SSL, from the begining. In my opinion, this is best practice for a well architected Saas service today.
In reading your question, I think you are over engineering it a little.
For a custom domain Saas app on the same server, you simply open port 80 to all traffic, regardless of domain name. Point all customer domains to
app.mystore.com, which is a CNAME to your app endpoint.
The app then reads the HTTP request header, and in that way determines the host name that was requested.
Finally the app looks up the host name in its client database, and locates the client record for the give customer domain.
For example, in Nxinx all you need is:
listen 80 default_server;
This server configuration provides a catch all for any domain that points to this endpoint.
That is all the web server should need to allow it to answer to any customer domain. The app must do the rest.
* When you serve a custom domain on an app on this domain, you should plan to serve the SSL endpoint for the domain, eg https://www.mycustomdomain.com. Consider this in your architecture design. Consider also the DNS issues also if your app fails over to a new IP.