Just checking why this is "hledal" here rather than "hledali" as the plural "jste" would imply. Is this formal address?
It's formal 2nd person masculine singular.
(The other possible translations are accepted as well, btw)
Is "jej" used as commonly as "ho" for "him" in speaking? Could this sentence also be:
"Hledal jste ho na novém letišti?"
I'd say 'ho' is definitely more common. And yes, your answer is correct too.