Ummm, hostage negotiations probably don't have a win-win, but I think that it's at least arguable that car sales and landlord-tenant negotiations do.
After all, it's a win-win for the car buyer to have a car and the car dealer to have some dollars (lose-lose would be for the car-wanter to have no car, and the dealer to have no dollars). Likewise with landlord-tenant negotiations: the tenant wins by getting a place to use, and the landlord wins by getting money. Sure, the tenant would like to use the place with no restrictions whatsoever, and the landlord would like all the money of the richest tenant ever, but there's a point where each gets enough of what he wants to make the deal worth making.
This is why it is easiest to negotiate when you don't actually need to.
Back then I didn't know the tricks of how to negotiate in such adversarial situations. Our goals were really just "raise rent vs. keep rent as is". You could say that it was still win-win, though, for example by pointing out that our secondary goals were to maintain good relations and not have any lawsuit.
"Real" negotiation takes place when there is no such equilibrium. For example, hostage negotiations, car sales, or a negotiation between a landlord and the tenant are of this sort. Maximizing your utility minimizes the other's utility, and vice versa. These types of negotiations proceed only by using psychology to trick the other side into making concessions. Being a tough guy is mostly counter-productive in such cases, too, it's more about exploiting cognitive biases like the anchoring effect. This activity is adversarial.
Good mediators are people who are able to turn such win-lose scenarios into real bargaining with win-win solutions, not by mere "reframing", but by really changing the decision/distribution problem. That's often possible, if you make the goals of the participants and broader setting/presumptions part of the negotiations.