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.