We study an extension of the vehicle routing problem with time windows by incorporating stochastic customers, i.e., ad-hoc service requests. The uncertainty in stochastic customers is captured through scenarios. Two a priori optimization approaches, a classical and a new one lead to two different problems, both of which are modeled as scenario-based two-stage stochastic programs. While the classical approach plans routes considering both regular and stochastic customers in the first stage and skips the stochastic customers who do not request a visit in the second stage, the new approach plans routes for regular customers in the first stage and inserts realized stochastic customers into the planned routes in the second stage. We prove that the new approach is not more costly than the classical approach. Then to solve the resulting problem, we propose deterministic equivalent formulations, strengthen them with valid inequalities and develop a Cut-and-Branch algorithm and an Integer L-shaped algorithm. The latter incorporates tailored optimality cuts based on the problem structure and several acceleration techniques. We also use a similar Cut-and-Branch algorithm to the solve the problem for the classical approach. Computational experiments are conducted to evaluate the effectiveness of the valid inequalities and the exact methods as well as the performance of the two a priori approaches, and to analyze the influence of insertion path flexibility on solution quality.