The main argument against fly still working while paralyzed is that wearing armor slows you, which means your limbs are involved somehow. That, and there being no concrete evidence in the rules that using fly is a mental action. On the other hand, a creature with no limbs and no movement modes can still fly under the effects of the spell, so maybe it should work. This question has some milage in it, and either result is reasonable.
Hold person, however, is a different question. It both paralyzes you and prevents you from taking actions of any kind. Flying, however done, is definately a move action.
--
gnfnrf