What I usually see in their requirements more likely looks like this: "must have the legal right to live and work in the EU"
I guess having the residency and work permit are enough to get considered for a flying job in Europe.
PS: Do you fly for MEA?