The problem with rebase is that it corrupts the true history of the commits. This doesn't show up on a smaller repo, but if you have a busy repo, with lots of contributers, untangling a mess becomes much harder if you no longer have the true parentage of a given commit.
Git rebase destroys the context of the commit, leaving basically a diff apply instead of the much more contextually rich merge commit. Yes, your repo looks messier, but it more accurately reflects the lifecycle of the code, and what the developer intended at each commit. If you really want a straight-line for your repos, why aren't you using something like SVN? Is the distributed nature of git really the big selling factor?
I've run teams that have used git how you are describing, always making people use rebase (in this case it was because we were syncing to SVN). Reconstructing what a developer did 4 months ago is much simpler with a merge vs a rebase. You can go to the merge just before the developer's first commit and see what the repo actually looked like when they started work. You can never do that with a rebase. The context in which the developer was working has been lost. Also, with multi-commit branches, you can see what the repo looked like after each commit. With a rebase, those intermittent commits are almost useless, as the repo doesn't look like it did when they made that commit.
To sum up, don't subvert git just because you want to see a straight line in your commit graph. It's not worth it, and it is ultimately a lie.