Infiniti2000 said:
If he's above the terrain, he's not in it.
I disagree. I don't think that this is a binary choice, where you're either in the terrain, or above it. What if I'm flying, but only a few inches off of the ground? What if I'm flying, but inside a cave?
While flying you are immune to the terrain movement penalties.
Are you? I am not familiar with that rule.
What "terrain" is the ocean?
I'm going to assume that it is "still water," which has the following effects:
Still Water: Lakes and oceans simply require a swim speed or successful Swim checks to move through (DC 10 in calm water, DC 15 in rough water, DC 20 in stormy water). Characters need a way to breathe if they’re underwater; failing that, they risk drowning. When underwater, characters can move in any direction as if they were flying with perfect maneuverability.
If you fly above the ocean, but not in it, can you breathe? Can a flying shark use its keen scent? After all, if flying is considered in the terrain, then certainly a flying shark is considered in the water. Right?
Characters need a way to breathe if they are underwater, but not otherwise. There are, then, some different degrees of "in the terrain."
I am not familiar with the flying shark, so I'll use a regular shark for reference... A shark's Keen Scent ability does not mention whether or not it can be used when not underwater, and neither does the description of the scent ability mention whether or not water-breathing creatures can use the ability when not underwater... So... Yes. Whether it is in the terrain or not.
A flying shark is considered in Still Water terrain, but Not Underwater... If it is flying, and not underwater. And, again... There is plenty of room for interpretation of in the terrain and not in the terrain without going to extremes.