Very interesting discussion. First off it's clear that different DM's will adjudicate this situation differently. That's one of the things I love about the 5th edition so far, and why it reminds me so much of the first and early second editions. The DM (and the players) can interpret the rules in the manner they see fit.
So here's my 2 cp.
Trenstemporal says "it can't be any clearer" and I agree:
Naturally Stealthy doesn't say you CAN hide even when obscured by a creature at least one size larger than you.
It says you can ATTEMPT to hide in that circumstance. There's a big difference. The halfling is so stealthy he can even hide behind somebody else, something that nobody else can do. BUT, the attempt still has to be successful.
So yes, very clear. But you have to succeed in that attempt to actually hide. So when anybody tries to hide, we've got to look at the actual rules for hiding:
When you try (attempt) to hide...
So this covers all attempts to hide, whether by special ability or not.
Until you are discovered or you stop hiding...
This directly implies that once you are discovered, you are no longer hidden.
You can't hide from a creature who can see you, and if you make noise...you give away your position.
Another clear statement that defines when you are discovered.
It also states that the DM might allow you to stay hidden...(if) a creature is distracted.
An example of an exception to the "you can't hide if your position is known" rule. The statement immediately prior specifically states that "In combat, most creatures stay alert for signs of danger..." so simply being in the midst of a combat doesn't qualify as a distraction. But it also indicates that there are circumstances where you still can attempt to hide
Now for invisibility, even if the opponent knows where you are you still have advantage to attack (per the condition). The logic for this is that even though you know their position, you can't see the attack coming. You don't know exactly when or from what direction it's coming. Is it a sword from the left, right, above? The invisible creature can see you and can easily modify it's tactics to hit you easier. Thus, advantage.
That's the major difference between invisibility and being hidden. It's also why the rules specifically state that always have advantage on your attacks when invisible, even if your opponent knows where you are.
With the halfling, the first attack, when you have no idea he's there, he can attempt to hide behind an ally. If successful he's hidden and has the advantage.
Once you know where the halfling is, you will be watching more carefully because you expect him to attack again from behind the fighter. And when he does that to make his attack, then you CAN see him. So he's no longer hidden, just concealed or obscured. He's probably harder to hit, but doesn't have an advantage to attack anymore.
Having advantage grants somewhere between a +4 and +5 to your attack. That's a hefty bonus and reflects that you actually have a significant advantage due to the circumstances.
So now the fighter throws sand into the eyes of the wizard while the halfling fakes starting to run behind a pillar across the room. Instead he quickly doubles back and hides behind the fighter again.
Of course a tactic like this would also only work a couple of times at most against any semi-intelligent opponent.
Now I would expect that there might be a Hide in Plain Sight ability for, say, a shadow. Something like:
Hide in Plain Sight: Shadows are so adept at blending into other shadows that they can attempt to hide even when they can be seen or their position is known.
So I agree completely, the rules are very clear. Once you can be seen or your position is known, you can't attempt to hide unless circumstances change. It's up to the DM to determine when those circumstances change, but for me stepping behind an ally isn't enough of a change in circumstances to allow another attempt.
Randy