Since @shosti pointed out that Evil considers deviation from Vim behavior as bugs, I filed a bug and one of the authors of Evil added a new possible value for
(setq evil-want-fine-undo 'fine)
With this setting, you get new undo units when moving the cursor in insert mode, but replace operations are undone in one step. As far as I can tell this is consistent with Vim. See here for details.