When properly operated, microgrids can facilitate the integration of stochastic renewable energy without compromising service reliability. However, in the context of multi-stage dispatching, finding the optimal day-ahead energy procurement that accounts for the variability of real-time operation is a computationally challenging task. This paper develops a computationally efficient two-stage economic dispatch scheme for a microgrid that exchanges energy with an external power system. The scheme is designed to minimize the generation and energy exchange costs, while setting limits on the microgrid-wide expected load not served. The day-ahead variables, which are the solution to the first stage, are found using a stochastic approximation saddle-point algorithm. The proposed algorithm is asymptotically convergent and can be efficiently implemented upon drawing samples from the distribution of the real-time state variables (wind energy, demand, and energy prices). Numerical tests using the IEEE 14-bus power system benchmark verify that the proposed scheme outperforms all other tested alternatives, even for very high wind power penetration.