To clarify and expand on the previous:

(defadvice evil-track-last-insertion (around
my-advice-evil-track-last-insertion activate)
  (my-msg "DEBUG: 01a evil-track-last-insertion match-beginning=%s
match-end=%s match-data=%s" (match-beginning 0) (match-end 0) (match-data))
  (save-match-data ad-do-it)
  (my-msg "DEBUG: 01b evil-track-last-insertion match-beginning=%s
match-end=%s match-data=%s" (match-beginning 0) (match-end 0) (match-data))
  )

Causes output:

2013-05-15T09:15:21.604604 DEBUG: 01a evil-track-last-insertion
match-beginning=0 match-end=5 match-data=(#<marker at 1 in Redacted.cc>
#<marker at 5 in Redacted.cc> #<marker at 4 in Redacted.cc> #<marker at 5
in Redacted.cc>)
2013-05-15T09:15:21.613707 DEBUG: 01b evil-track-last-insertion
match-beginning=1 match-end=5 match-data=(#<marker at 1 in Redacted.cc>
#<marker at 5 in Redacted.cc> #<marker at 4 in Redacted.cc> #<marker at 5
in Redacted.cc>)

(match-beginning 0) evaluates to 0 while the first element of (match-data)
is a marker at 1. Is this discrepancy expected?

I determined the reason for the discrepancy is that when match-data creates
the markers, set-marker can adjust the position. This puts the markers
saved and restored through save-match-data out of sync with the
search_regs. I suspect this is a problem since replace-match assumes
search_regs don't change during change hooks. It certainly creates a
problem for the error checking approach.