In the sampling I have rejected 49% of actual function evaluations. Those rejected evaluations could have provided me a bigger insight of the objective function. Is that so?

In addition to what Tim said about this, MCMC produces samples that are correlated and MC produces independent samples. If the rejection rate is low, and you accept almost all proposals, then that means that you are probably going to a value that is very close to the previous value. This increases autocorrelation in your samples and thus provides less power. For this reason, when using MCMC it is known that an acceptance probability of around 20 - 40% is good.

Is MCMC better than MC for "mapping" a very complicated black box function, given that I would reject many costly function evaluations?

In theory, if you can do Monte Carlo (MC), there is no reason to do Markov chain Monte Carlo (MCMC). Why? Because MC produces independent samples from the exact target distribution and MCMC produces correlated samples approximately from the target distribution. MC trumps MCMC. So if the target distributed is a known distribution (like Normal, t, $\chi^2$ etc), you should just use Monte Carlo.

However, if a distribution is unknown (like in most Bayesian settings), you can't just use on the shelf software techniques. So for MC you generally use Rejection Sampling. This Monte Carlo technique also proposes a value to be accepted or rejected, the difference is that if values are accepted, they produce iid samples from the target distribution. In RS, you want as high an possible acceptance rate.

You run into trouble when the target distribution is high dimensional (even as high as 10). Because, in RS a vector of values is proposed and the whole vector is accepted or rejected. This reduces the acceptance rate, sometimes to the extent of a .0000001 acceptance rate. So you will have to wait a long time for even 1 acceptance. In MCMC, you can use variable at a time Metropolis Hastings to propose a new value for each variable, and this maintains a good acceptance rate for each value.

The reason MCMC methods are used so much is because most Bayesian posterior distributions are high dimensional, and thus automatically, even if a RS can be implemented, it will be very slow.

In the sampling I have rejected 49% of actual function evaluations. Those rejected evaluations could have provided me a bigger insight of the objective function. Is that so?

In addition to what Tim said about this, MCMC produces samples that are correlated and MC produces independent samples. If the rejection rate is low, and you accept almost all proposals, then that means that you are probably going to a value that is very close to the previous value. This increases autocorrelation in your samples and thus provides less power. For this reason, when using MCMC it is known that an acceptance probability of around 20 - 40% is good.

Is MCMC better than MC for "mapping" a very complicated black box function, given that I would reject many costly function evaluations?

In theory, if you can do Monte Carlo (MC), there is no reason to do Markov chain Monte Carlo (MCMC). Why? Because MC produces independent samples from the exact target distribution and MCMC produces correlated samples approximately from the target distribution. MC trumps MCMC. So if the target distributed is a known distribution (like Normal, t, $\chi^2$ etc), you should just use Monte Carlo.

However, if a distribution is unknown (like in most Bayesian settings), you can't just use on the shelf software techniques. So for MC you generally use Rejection Sampling (RS). This Monte Carlo technique also proposes a value to be accepted or rejected, the difference is that if values are accepted, they produce iid samples from the target distribution. In RS, you want as high an possible acceptance rate.

You run into trouble when the target distribution is high dimensional (even as high as 10). Because, in RS a vector of values is proposed and the whole vector is accepted or rejected. This reduces the acceptance rate, sometimes to the extent of a .0000001 acceptance rate. So you will have to wait a long time for even 1 acceptance. In MCMC, you can use variable at a time Metropolis Hastings to propose a new value for each variable, and this maintains a good acceptance rate for each value.

The reason MCMC methods are used so much is because most Bayesian posterior distributions are high dimensional, and thus automatically, even if a RS can be implemented, it will be very slow.