I also am a non EU Citizen with a permanent residency status in Germany (waiting for my citizenship application to finish this summer). It seems most of the airlines in Europe are requiring a EU Passport which obviously means holding a citizenship. In Germany, on the other hand, all airlines seem to accept a German permanent residency.