It isn't great when staff tell a fib, but management aren't blameless in causing this. Not to excuse lies per se, but I think a touch of sympathy might be appropriate.
The staff are often dealing with highly articulate, and knowledgeable and demanding customers in a public place where everyone else is listening and have often been given instructions by their management to do things that they do not wish to argue about and debate in public and the way they sometimes deal with it is by a fib. If they keep passing angry customers onto their boss they risk their own jobs. It might seem better to them to say "I'm sorry the upgrade isn't available" than say "It is available but we have a policy of holding onto them in case we can sell them later .... we'd prefer to keep if free than give it to you ... would you like to complain to my boss?"
Just saying we should be being much more sympathetic to staff when dealing with them in this situation and perhaps be saying instead "I really understand the position you're in. Would you mind calling the Duty Manager, and asking him to come and talk to me", so long as you are only being deprived of entitlement when you are certain it is available.
This issue is about hotel policy, and checkin staff don't make hotel policy. It is normally managements' fault but they are hiding in their offices and letting their junior staff take the flak. Take it out on management, not on the people in the line of fire.