Hinn 24. maí 2004 sendi Persónuvernd Flugleiðum hf. bréf þar sem óskað er skýringa í tengslum við væntanlega miðlun upplýsinga um flugfarþega og flugáhafnir frá félaginu til bandarískra stjórnvalda samkvæmt kröfu þeirra þar að lútandi, þ.e. svonefndra APIS/PNR-upplýsinga úr bókunarkerfi félagsins. Hér eru nánari upplýsingar um málið .