It's taken me a while to come around, but you'd have to pry rebase out of my cold dead hands now.
I have not found it to happen often though, for two reasons. First, it is widely agreed upon among almost all mildly experienced to highly experienced Git users that rewriting published history is a bad thing. Second, if it becomes a problem with new Git users doing this, you can turn of non-ff updates in the public repository, thereby disallowing this to ever happen, unless you go through all the steps to delete and recreate a branch.
If you're working with your local unpublished history, then it is your responsibility to make sure they still make sense in the context of newer updates from the public repo regardless of whether you rebase or merge. I can see how it would be confusing if people failed at this. I tend to find that more confusion results from people inflating the history with loads of one-commit merge bubbles everywhere rather than just rebasing their small changes.
I have never understood the problem that some people have with the idea of rewriting history. It's as if the very idea of it offends them. Do file system writes also put you off? Is it important that I see the history of every single keystroke you made while twiddling with your config file? When you fixed a typo you made in a comment before publishing your change, how is this not a "rewrite of history for aesthetic reasons"? Do you really need to know about all the tens of little WIP commits I made because I just wanted to back up my changes before going to the bathroom? Am I not allowed to clean up a little bit before I publish all my own changes to the world?
Now if you're just talking about rewriting published history, then nobody is going to disagree with you.