Hi Kai,
I am not sure what you want to improve in Example III. The interval fminsearch function's focus is to find fval. If you are interested in the corresponding x values, you can find them with the interval fsolve function. Use optimset parameters on either function to improve accuracy.
I must agree that the function is not very useful as a generic tool, because it doesn't do much more than "min (f (meshgrid (...)))" would do. I would consider to use it in special cases where I know that my grid is good and not too big.
There is no bisection or heuristics of any kind, so all we have is a "brute force" attempt to traverse the grid.
Oliver

Please don't feel discouraged, but I really want to understand, what makes your function better than existing tools.
Looking at your examples, I don't like them, as they only reveal things I don't understand about your algorithm or need more documentation:
Example I  is in my opinion as elegant as writing the code of comment #1, and the results are only as good as choosing the grid.
Example II  has four equal minima on each edge of the grid! Here the code of comment #1 would even perform "better". This behavior of finding only one (and which one?) minimum must be clearly documented to be reliable.
Example III  My understanding of the example is a minimum near [100 100] with fval=10. Maybe document this, it is tedious to find out.
Moreover I think this example just shows the feature of function handles and totally misleads, what fgridsearch should do.
fgridsearch does not (as I thought) search in this example for a minimum on the grid using fminsearch to help this. The returned params lies on the grid
but the function value for params is not the minimum!
It is just a point from the grid, that converged to the smallest local minimum MAYBE on the grid, as fminsearch embedded in @gh does not care about the given grid. In the following input, the starting point lies on the grid, but converges outside, and this is what fgridsearch would return without any warning for this example!
I think for global optimization the overloaded fminsearch for intervals http://octave.sourceforge.net/interval/function/@infsup/fminsearch.html
does a "better" job. I respects the boundaries and delivers rigorous inclusions. Using the interval package, I get:
Here I am sure to find the global minimum within these bounds. I added the package maintainer, maybe he can give a hint on how to improve Example III with his interval package.

I improved the documentation a tiny bit. Most importantly, I added another example which demonstrates more clearly why I consider fgridsearch to be beneficial. I'll copy the example here for convenience:
I have to admit that this function only helps to hide loops, though.
If the new example makes the function interesting, I'll happily work on the other points.
(file #37315)

This function basically does something according to the following code:
Some points to consider:
1. This function is not MATLAB compatible. Is there a particular reason/scientific discipline, that needs this function and is not able to write code, like the small listing above?
2. The documentation is not very detailed, better document the input and output. See other Octave functions as guideline:
http://hg.savannah.gnu.org/hgweb/octave/file/74a676d5ce09/scripts/optimization/fminsearch.m
3. Does this function work for dimensions > 2?
4. How does this function perform for large scale problems?
5. I notice function crashes, without help for the user, for nonconforming input like
To sum up, I don't see the benefits of this function. If one needs to evaluate the whole optimization domain, like fgridsearch does, one will code something like in this post above. fminsearch addresses another use case, where only the optimum matters and from this point one can try to evaluate a local grid, to save lots of computational effort.
