If I were to cast levitate on a prone orc and float him 20 feet into the air - would he still be prone? - Yes
Jeremy Crawford has clarified:
You can almost always be knocked prone. About the only time it's physically impossible for you to be knocked prone is when you're affixed to something that keeps you upright.
and further:
Being underwater doesn't stop you from being knocked over. Hovering also doesn't stop you from being knocked over, but hovering does stop you from falling when you're knocked over in the air.
The prone condition does not have a requirement that the creature be on the ground. In fact, even flying creatures (as you correctly said) and swimming creatures can be prone.
The only thing that would prevent a creature from having the prone condition would be a specific effect (from a spell or the like) or from an immunity that would be listed in their stat block.
So barring any of the above immunities, the levitated creature would suffer all of the effects of the prone condition as listed in the PHB.
Flavor
Prone as used in D&D 5e is not what we traditionally think of when we hear the word: lying flat on the ground. Instead it is better to think of prone in D&D as a creature being in a position that is unfamiliar or inconvenient to them thus requiring to right themselves and putting themselves at a disadvantage.
For a levitating creature they may be upside down or tangled up in their stuff or any variety of other circumstances that fits the above.
A good comparison might be how Jeremy Crawford describes a creature knocked prone underwater:
If you're knocked prone underwater, you're subjected to the effects of the prone condition as normal. One way to visualize it is that you're floundering.
"Prone" is a game term first and foremost
It is important to remember that "prone" is a defined game term, with set conditions and effects. Always think of it in that sense even though it carries slightly different connotations in plain English. Some cases of being "prone" don't make sense from a physical perspective when thought about in non-game terms, but that is fine because D&D only uses prone to describe a condition that is imposed on creatures. How that manifests is up to the DM and players to work out.