1. Revision histories which are "deleted" are simply marked as such. They are not removed from the history graph.
2. Marking a revision "deleted" is itself a revision update. Maybe a way to think of it is a Git annotated tag.
Conceptually, a delete could look like this:
A1 -> B2 -> B2_Deleted
So yes, if you pull again and you see B3, no problem. Just put it on the revision tree. B3 and B2_Deleted are siblings with parent B2.
For example, what if B3 stores "delete_account: true" which means in this application that the user wishes to completely remove his account and delete all of his data. Clearly that fact is dominant in the merge/conflict-resolution strategy and it hardly matters what the history graph looks like.
Finally, the history graph is always there for the client (replicator). There is nothing stopping an application-level `git-rerere` implementation--perhaps as a library which all developers could use.
(Note, I'm not saying explicit merge info isn't useful. For all I know it was overlooked in the original architecture. I'm just saying it's not a showstopper.)