Notice that the "First-order optimality" measure at the point found by fmincon in Loop #2 is lower than the starting point found by patternsearch. Unlike patternsearch, fmincon uses the function's derivatives to compute the first-order optimality (a measure of stationarity), and thus to see if it is worth continuing to iterate. Clearly, the point x0 found by patternsearch was not stationary enough for fmincon to see it is a solution. It therefore continues to iterate until it finds a more stationary point.
My guess is that your function might not have continuous derivatives, as is required by fmincon. When fmincon finds a point, patternsearch can therefore throw it out of stationarity with a slight perturbation. Alternatively, patternsearch may have found a non-stationary point that was far away from the one obtained in Loop #1, but with a similar objective function value.
In any case, it might help to know what fmincon algorithm you are using (sqp, interior-point, etc...)
