I was looking at the WFS-T response for Inserts (it's a list of FIDs). The spec says these should be in the same order as the features in the request's Insert elements.
However, I'm seeing these in a "strange" order. I think I've tracked it down to the DefaultFeatureCollection implementation. This stores the features in a SortedMap<String, SimpleFeature>, and the iterator just returns them in the text-natural-id-order (ie. "new0", "new1", "new11", "new2", "new3",... – "new11" is in the wrong order). This messes up the order of the new fids for the inserted features.