This is why people don't like rebase, but if you just tell people "never start a rebase farther back than master" the problem magically goes away. Tada!

It's even simpler and more general than this: don't rewrite public history. There, you're done.

I'd add that it's only a problem as team size grows. If the only other people who might be affected are sitting nearby, I can say "has anyone pushed since <commit>" and happily push -f my rebase in most cases.