PrinceOfFacade
Ghost-Type Master
Scyther is in the same boat as quite a fair number of Pokemon in that regard. Scyther is capable of flight, and thus it can participate in Sky Battles; whether or not you think it's illogical that Scyther can't learn Fly, its eligibility for Sky Battles has nothing to do with it.
Dang it, it should be able to learn Fly. Point blank.
If a 1'4" bird can carry us across the sky, then a 4'10" flying praying mantis should be able to.