> Can you show us the offenders?

Offenders and status:
   semantic-change-function      Fixed in CEDET mainline
   evil-ex-search-update-pattern Fixed in Evil mainline
   evil-track-last-insertion     See below
   Undo tree                     Haven't investigated

I'm not so sure search_regs are saved and restored through save-match-data.
I have this advice:

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

Note: my-msg is like message but prefixes the time.

When I inserted a new line in a .cc file, I get:

2013-05-14T12:51:39.010590 DEBUG: 01 evil-track-last-insertion
match-data=(#<marker at 1 in FileNameRedacted.cc> #<marker at 5 in
FileNameRedacted.cc> #<marker at 4 in FileNameRedacted.cc> #<marker at 5 in
FileNameRedacted.cc>) match-beginning=0
2013-05-14T12:51:39.020153 DEBUG: 02 evil-track-last-insertion
match-data=(#<marker at 1 in FileNameRedacted.cc> #<marker at 5 in
FileNameRedacted.cc> #<marker at 4 in FileNameRedacted.cc> #<marker at 5 in
FileNameRedacted.cc>) match-beginning=1
ad-handle-definition: `semantic-change-function' got redefined
2013-05-14T12:51:39.023610 DEBUG: 01 semantic-change-function
match-beginning=1
2013-05-14T12:51:39.025341 DEBUG: 02 semantic-change-function
match-beginning=1
2013-05-14T12:51:39.025525 DEBUG: 01 c-after-change match-beginning=1
2013-05-14T12:51:39.026920 DEBUG: 02 c-after-change match-beginning=1
2013-05-14T12:51:39.027110 DEBUG: 01 jit-lock-after-change match-beginning=1
2013-05-14T12:51:39.027319 DEBUG: 02 jit-lock-after-change match-beginning=1
newline: Match data corrupted in after-change-functions. Consider using
save-match-data

In this case, the change of match-beginning from 0 to 1 in
evil-track-last-insertion causes the error.

For reference, I am currently using the attached patch, which incorporates
your feedback.