I've flown all over Europe with non-EU nationals and never had any trouble; as long as they had already entered the EU by a legitimate route. I've even flown in and out of the UK with a friend from Singapore; no problems. I flew with my Chinese girlfriend all the way from Rotterdam to Egypt and back, and the also Tunisia and back, stopping off in many different EU and non-EU countries; no problems at all (she had visas for Egypt and Tunisia of course).
Of course, this doesn't mean it's allowed