Note this line:

 ancestor fdedead1b396 local fdedead1b396+ remote fdedead1b396

The trouble here is really that we're updating from revision 'tip+' in the
working directory to revision 'tip'. That is, we're going backwards in time. And
the merge logic for going backwards is very different from the logic going
forward. If we go backwards in time, it's quite natural to reinstate deleted
files and so we do.

So the problem seems to actually be that we shouldn't try to update in this
case, not that there's anything wrong with the merge logic itself.

Updating title.