Robust black box function minimization with extremely expensive cost function

I've read the paper, but never used the approach.

"Efficient Global Optimization of Expensive Black-Box Functions" by: Donald R. Jones, Matthias Schonlau, William J. Welch

PDF available from one of the page of an author.

You haven't said so explicitly, but it sounds as though your function evaluations may also be noisy in that the function value is the result of a Monte Carlo simulation that incorporates random numbers. If that's the case then you definitely want to look at response surface modeling, since methods that attempt to approximate derivatives by finite differencing don't work in this situation and even pattern search methods like Nelder-Mead can be easily fooled by one bad function evaluation.