Naughty undo-tree

From time to time undo-tree behaves strangely. With a single undo step it can undo a char insert or whole paragraphs that took several minutes to enter. Worse, sometimes it fails while trying to redo with:

primitive-undo: Unrecognized entry in undo list undo-tree-canary Combined with one of those huge undo steps, this amounts to serious data loss. Does someone else experience these problems? Is Evil handicapped in some way if I stop using undo-tree?