Freedom of Movement explicitly disallows the application of two conditions to the subject of the spell, namely they can't be paralyzed nor restrained.
Stunned is also a condition. It is not listed under FoM as disallowed. Stunned also does not reduce the target's speed. It states that the target can't move, whereas other conditions, as you noted yourself, explicitly state an altered speed value.
The paralyzed condition is almost the same as the stunned condition, the only differences being that 1. a paralyzed creature can't even speak falteringly, 2. attacks targeting a paralyzed creature and coming from an attacker within 5 feet of the paralyzed creature are critical hits. Paralyzed inflicts another condition, incapacitated on the target. So does stunned. Stunned does not inflict paralyzed on the target. FoM explicitly disallows paralyzed, but it does not mention stunned, ergo FoM does not protect against stunned, nor against spells that apply stunned, such as Power Word Stun. Considering there's no Power Word Paralyze and no Power Word Restrain, this seems to be a conscious design choice.
I'm not sure I like this, but this is how I read RAW: FoM does not allow movement when its target is stunned regardless what applied said condition to its target (and no matter that stunned is a weaker version of paralyzed.)
-
RAI I think the reasoning behind this is that stunned affects your mind, not your speed. Your speed is the distance the creature can cover. When stunned, its speed is the same, only the will to cover the distance unaffected speed would allow it to cover is impacted. (Also, the word "move" in the definition of stunned covers not just the movement of the legs or similar which allows the creature to go some distance. A stunned creature doesn't gesticulate, etc either. At least in my interpretation.)
(PHB 5e 1st printing, 2014, no errata, pages 244, 291-292)
The Second Key Is Found
I'm afraid my answer falls into "well-reasoned" (or at least I hope it does), but I would have a hard time being sold on the idea that the spell fails because a key is closer but concealed by lead. If the spell fails, that means the spell identified a key within a lead box and knew it needed to fail... which kind of means it succeeded, because the spell broke through the lead to identify the key, which is the only object that could have been in there that caused it to fail.
The game we play is filled with magic, yes, but I think we all like it to be "logical magic" insofar as that phrase makes any sense. Option #1 is much more believable than Option #2.
Best Answer
The Beholder's Telekinetic Ray does not deal damage
This is regardless of the Fly speed of the creature. What the Telekinetic Ray does is restrain the target if they fail their Strength save, and then move them 30 ft in any direction.
A Flying creature does not take Falling damage
See this answer, which quotes PHB 191, Flying Movement.
If the Beholder used a Telekinetic Ray to move a flying creature above a pit and then releases it with the intent of letting it fall to its death, if it's being held aloft by the Fly spell, it stays afloat.
If the target has wings instead and so it has a mundane, non-magical way of flying, as the target is being released from the Telekinetic Ray's effects, the Restrained condition is lifted. This grants the creature its speed back, including its Fly speed. Since it wasn't knocked Prone, then it can remain flying.