I'd like to also point out a core naturally (ie, absolutely not via magical means) flying monster that gets evasion as a racial quality, the Giant Eagle.
To me, assuming you have at least good maneurability, it'd be even easier to evade in air that on the ground. You've got a full 3 dimensions of movement to go in to avoid getting harmed.