Lots of criss-cross merges make it really difficult to follow history, making it less useful.

Note that merge vs rebase a false dichotomy. After rebasing you still have to merge your branch anyway, either fast-forward or with an explicit merge commit.

In the end, it's about commutating your changes effectively. The less noise there is, the better you can communicate. That takes effort from both sides, but many persons put all the burden on the receiving side.