Olaf, I agree that we do not expect to reproduce the Matlab results in all cases, especially in more 'difficult' or ill-posed problems -- but this is also true for functions in core Octave that aim to have the same syntax as Matlab, for example inverting an almost singular matrix may well give different numbers in Octave than in Matlab. Numerical approximations will unavoidably have some implementation dependence.
In terms of algorithms, it looks like the Optimization package has __lm_svd__, which offers a Levenberg-Marquardt algorithm for least squares (with arbitrary constraints allowed, if I understand it correctly?). The other algorithm Matlab offers in lsqcurvefit and lsqnonlin is a trust-region one[1] which supposedly can be more efficient for high-dimensional problems -- is anything like that implemented in Octave?
--Nir