First of all, fminsearch is NOT a gradient descent algorithm. Calling it that does not make it one.
Second, large residual problems are classically a bane for nonlinear least squares. This is well known. Ok, it should be well known, as I recall reading about the issues 35 years ago or so. For example:
Note the date.
Do you want to use particle swarms or genetic algorithms or any other stochastic optimizer? Not really a good idea, IMHO, since those schemes use LOTS of extra function evaluations while still walking down hill. They are as much (or little) a gradient descent algorithm as is fminsearch. They can be more slowly convergent in general though.
I don't have your model at hand, so it is somewhat difficult to make constructive suggestions. My first choice to improve robustness of large residual problems would be a partitioned nonlinear least squares tool. But that requires the ability to partition the unknowns into a conditionally linear subset, and an intrinsically nonlinear subset. Since your model is a simulation, that may well not be an option.
My second suggestion is to use a robust solver. Nlinfit from the stats toolbox does offer a robust option.
Third, you will benefit greatly from good starting values for large residual problems.