I think you could say that in both groups, people are objecting because society is not distributing resources according to some norm of what qualities the resource distribution is supposed to be based on.

In the first group of examples, people are deceiving others and violating agreements, and society says that people are supposed to be rewarded for honest behavior and keeping agreements.

For the second group of examples:

• The homeless person example is a bit tricky, since there are multiple different norms that they might be appealing to, but suppose that the homeless person used to be a hard worker before he got laid off and lost his home. The homeless person may then be objecting that society is supposed to reward a willingness to put in hard work, whereas he doesn't perceive the millionaire as having worked equally hard. Or, the homeless person may think that society should provide some minimum level of resources to everyone, and the fact that he has nothing while another person has millions demonstrates a particularly blatant violation of this rule.
• There's a social ideal saying that people should be rewarded for their "internal" characteristics (like honesty) rather than "external" ones (like appearance), so the unattractive girl is objecting to the attractive girl being rewarded for something she's not supposed to be rewarded for.
• The house owner is objecting because we usually think that people should be allowed to keep the property they have worked to have, and the eminent domain claim is violating that intuition.
• The union contractor is complaing because he thinks that being unionized provides benefits for the profession as a whole, and that the non-union contractor is getting a personal benefit while defecting against the rest of the profession.

Regardless of what your ideal society looks like, creating it probably requires consistently maintaining some algorithm that rewards certain behaviors while punishing others. Fairness violations could be thought of as situations where the algorithm doesn't work, and people are being rewarded for things that an optimal society would punish them for, or vice versa.

You could also say that in both groups, there is actually an implicit agreement going on, with people being told (via e.g. social ideals and what gets praised in public) that "if you do this, then you'll be rewarded". If you buy into that claim, then you will feel cheated if you do what you think you should do, but then never get the reward.

Of course, the situation is made more complicated by the fact that there is no consistent, univerally-agreed upon norm of what the ideal society should be, nor of what would be the optimal algorithm for creating it. People also have an incentive to push ideals which benefit them personally, whether as a conscious strategy or as an unconscious act of motivated cognition. So it's not surprising that people will have widely differing ideas of what "fair" behavior actually looks like.

I find it strange that the same phrase is used to refer to such different things.

However looking at reality, the phrase is used in all these ways, isn't it?

I was specifically trying to choose examples

That's a bias, isn't it? :-)

If you're choosing examples to construct a definition from, already having a definition in mind makes the exercise pointless.

If you choose examples of fraud and abuse of power you essentially force the definition of "unfair" be "fraud and abuse of power".

There is a subtle, but important difference. Many people (here and elsewhere) would consider the exercise of eminent domain powers by the state to be ethical and correct application of state powers for the betterment of society -- a few suffer but for the greater good.