I believe lots of people do not understand that you should treat remote branches differently than local branches. More precisely, you treat remote/global history differently than local history.

Using rebase to clean you local history is ok. Maybe even recommended or mandatory depending on the project. Changing history, which is already in other people's repos, will lead confusion and should really be avoided.