To clarify what I mean above: I'd be inclined (perhaps unhelpfully) to think of this as minimising $f:\mathbb{R}^{4 \times 4}\to \mathbb{R}, A\mapsto \sum_i\left|\left( \begin{array}{cc} M_i & 0 \\ 0 & 1 \end{array}\right) A \left( \begin{array}{c} p_i \\ 1 \end{array}\right)\right|^2$ subject to some constraints which keep $A$ on the manifold of rigid motions. I don't claim to have any expertise in this area, but I like the question so I thought I'd post in case it helps (sorry if you've already tried something like this).

This looks a bit like a Lagrange multiplier type problem no?

I don't have a copy to hand (so might be completely wrong), but I seem to remember there being quite bit about this sort of thing in the book "An invitation to operator theory" by Abramovich and Aliprantis. It's a nice book in any case,

Taking small steps during the iteration does seem sensible. However, it also restricts how far the simplex can travel for a given number of function evaluations, and isn't always under my direct control: I guess I could restart my iteration if I find the step-size is getting too big...

Any and all comments are very welcome! I think my preference would probably be using the exponential map given the choice (I mentioned Euler angles simply because it was the first thing I tried when I coded this up). I have heard of people using the unit quaternions, but I'm not sure that's so different from working in $SO(3)$ without co-ordinates (apart from maybe reducing the number of multiplications slightly).

I should probably say: what I'm really interested in here is whether pulling back to $\mathbb{R}^3$ is intrinsically problematic when using Nelder-Mead for this type of problem (each $f$ actually represents a toy problem where I already know the global minimum).

It was quite a long second. They have a habit of being longer than usual when I'm busy with other things... That is to say, sorry for the delay!