Indeed there is a small slow down for insertion at the beginning.
However, this is simply due to the extra function _index() and thus linear in the number of insertion operations.

My patch essentially boosts insertions before /any fixed/ node.
If this reference node changes between insertions (as in your "before first" example), there is no gain anymore.

Of course, this optimization comes at the cost of an additional integer per node. There is no free lunch!

I know, that there are other parsers (e.g. etree) available. However
changing my existing code base from minidom to etree will be a heavy change, which isn't easily accepted as well.

I think, my minidom patch is a clean and simple fix to a common performance issue. As it mostly effects 2.7, it should primarily go there ;-)