I worked for an 'on-demand' startup facing this problem and we simply ran a limited experiment which showed users full availability. We tried to back-fill any appointments for which we didn't have real supply, but otherwise sent out an 'oops' email and rescheduled.

While there was clearly a negative experience for the customers who went through the experiment and had appointments rescheduled, we did get a very good measure of true demand and were able to optimize some of our supply dynamics.