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!
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.
