Q:

How can I get undo behavior in Evil similar to Vim's? 

The default undo behavior in Evil is too coarse-grained because it considers anything taking place between entering insert mode and leaving it as one edit operation.   When you enter a whole paragraph of text during one insert and then execute undo, the whole paragraph is removed.   In contrast to that, Vim starts a new undo unit whenever you move the cursor in insert mode by means other than entering text. 
Evil has a customization variable that can be used to get a more fine-grained undo history:
(setq evil-want-fine-undo t)

With this setting, Evil starts a new undo unit when the cursor is moved in insert mode, just like Vim does.   However, this setting also messes with how the replace operation is handled: if you replace a word using cw, you have to undo twice to restore the original word: once for removing the new word and once for reinserting the original word.   This is inconsistent with Vim and doesn't make much sense because replace should be atomic. 
The question: How can I configure Evil and undo-tree in order to get Vim's undo behavior? 

A:

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 evil-want-fine-undo: 
(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. 

A:

According to the variable description (see C-h v evil-want-fine-undo) the value fine is not supported any more due to inconsistent behaviour.  
As I use undo to undo typos or the mentioned setting helped my allot. 
(setq evil-want-fine-undo t) 

I had trouble undoing errors in org-table formula editing, since you don't have to leave the insert mode if you want to change to *Edit Forumlas* with C-'.