I really hope that they tried to get the records through a court request to the right people rather then just calling the company and asking for it. I find it really unlikely that such records don't exist anymore. Phone call billing is the one thing that brings money to telcos and they're often processed and analysed. They may not be exposed to public, but not keeping a backup of them stored at least on some tapes somewhere for years is really surprising...