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.
Here's it using the DefaultFeatureCollection;
https://github.com/geoserver/geoserver/blob/2.9.x/src/wfs/src/main/java/org/geoserver/wfs/InsertElementHandler.java#L98
and the passing it (incorrectly ordered) off to the underlying datastore;
https://github.com/geoserver/geoserver/blob/2.9.x/src/wfs/src/main/java/org/geoserver/wfs/InsertElementHandler.java#L189
Here's the DefaultFeatureCollection implementation;
https://github.com/geotools/geotools/blob/master/modules/library/main/src/main/java/org/geotools/feature/DefaultFeatureCollection.java#L330
