I gave up on git rebase after getting exactly the problem you describe, when trying to rebase my temp branch (with new stuff, including files that were entirely commented out in one commit then deleted in the next) on top of my main branch (with fixes to stuff the temp branch deletes or changes). I'd rebased things before, mostly because I'd heard it was what you were supposed to do, and it hadn't been a problem those times, but this time was awful!
Lots of tiresome conflicts, as git kept badgering me about merge conflicts due to one branch commenting out what another branch had changed, all in a file that would be deleted by the next commit. Of course, none of this crops up during a merge, because it only needs to consider the results rather than each intermediate step - so the merge ended up being much neater. (I think there ended up being fewer merge conflicts across the whole merge than there were in one file in the first step of the rebase.)
The idea behind this was that I'd rebase, then use rebase -i to remove the separate cleanup steps, then I could merge into the main branch, and it would be a nice fast-forward. I don't like the idea of using rebase -i until I've got something rebased as it stands, but it seems that git isn't always going to make that easy.
Since then, I've stuck with git merge, and indeed I've come to quite like seeing where the merges are in the history. That was something I found useful about Perforce's Revision Graph display, too.
