If you have a failure, having a straight-line history makes it easier to do a bisect with your failing test and find the point of failure.
Unrelated to your issue with git rebase, but addressing another common complaint, git rerere allows git to remember and reuse previous conflict resolution so you don't get into resolution hell.
But thanks for git rerere! I've never heard about it.
Having a merge marker showing where the commits came from and the branch name is incredibly useful, but that's not a black mark against rebase -- only your organisation's lack of diligence to following a set of rules.
If you use something like Github's pull request system it will always create a merge commit when you merge a pull request; as it should be.
One thing you can do whilst rebasing to ensure the rebasing doesn't break against the master branch you're rebasing against is calling out to a shell command -- rebase will let you do this -- to run your unit tests between each rebase commit.
Nice shell tip!
In the original commit before rebase everything seemed to be working; but someone changed something else in the code you were relying on without creating a direct conflict, and now all your rebased commits crash and burn. What's worse, you discover it much later, when original commits are long gone, and instead of one merge commit being the easy traceable breaking point, you now don't even quite remember which exact commits were rebased and have to check EVERYTHING.
Or, and with merge commit you could've easily just check it right there with simple tests before committing — no such convenient option for rebase.
The thing is, it's a leaky abstraction. Rebase workflow tries to present things simpler then they really are, and you end up paying a price for it.