[Adding Toby, since I mention undo-tree.]

> It would also be more conservative to keep this unchanged, but I
> think I agree with you here that we don't need to be *that*
> conservative.

This is how I addressed that:

diff --git a/lisp/simple.el b/lisp/simple.el
index 4a3a89c..6b5031e 100644
--- a/lisp/simple.el
+++ b/lisp/simple.el
@@ -2375,6 +2375,10 @@ we stop and ignore all further elements."
                    ;; This is a "was unmodified" element.
                    ;; Keep it if we have kept everything thus far.
                    (not some-rejected))
+                   ;; Skip over marker adjustments, instead relying on
+                   ;; finding them after (TEXT . POS) elements
+                   ((markerp (car-safe undo-elt))
+                    nil)
                   (t
                    (undo-elt-in-region undo-elt start end)))))
        (if keep-this
@@ -2461,7 +2465,7 @@ marker adjustment's corresponding (TEXT . POS)
element."
              (<= (abs (cdr undo-elt)) end)))
        ((and (consp undo-elt) (markerp (car undo-elt)))
         ;; (MARKER . ADJUSTMENT)
-         nil)
+         (<= start (car undo-elt) end))
        ((null (car undo-elt))
         ;; (nil PROPERTY VALUE BEG . END)
         (let ((tail (nthcdr 3 undo-elt)))

It maintains the same return from undo-elt-in-region for marker
adjustments as before.

I took a look at undo-tree. It doesn't use undo-make-selective-list,
but does use undo-elt-in-region. I guess that means this particular
bug won't be fixed in undo-tree for regional undos, until it also
scans forward from (TEXT . POS) as this patch's
undo-make-selective-list does.

> Begs the question: why didn't (don't) we record marker adjustments
> here (and other similar places)?

I considered pursuing that question earlier, but opted for those
callers to behave as before, at least for now.

There's a related comment nearby one of the callers:

/* Note that this does not yet handle markers quite right.
   Also it needs to record a single undo-entry that does a replacement
   rather than a separate delete and insert.
   That way, undo will also handle markers properly.

   But if MARKERS is 0, don't relocate markers.  */

I've attached the updated patch with your comments incorporated. I'll
install soon.