This is a common misconception. Ever since the Telephone Records and Privacy Protection Act of 2006[0,1] was passed, it has been illegal to obtain telephone records if you're not a law enforcement or intelligence agency.

Edit: Here[2] is a more comprehensive list of records that private investigators cannot legally obtain: banking and financial records, telephone records, credit information, nationwide criminal records, and a comprehensive individual profile. However, I have no confirmation of the veracity of that website, as I just found it with a quick search.

0: http://en.wikipedia.org/wiki/Telephone_Records_and_Privacy_P...

1: http://www.gpo.gov/fdsys/pkg/BILLS-109hr4709enr/pdf/BILLS-10...

2: http://www.diligentiagroup.com/legal-investigation/5-myths-w...

I think most of definitions of "telephone records" involve call history and other stuff that got HP board in trouble.

Here something like a credit statement showing consistency of payments to a mobile operator would suffice - with number portability being a law some brokers would sell you access to a database telling you which carrier the number belongs to, and how long ago it was recycled.

Well, like I said above, credit information is also not so easy to obtain.

But remember, this is all when you're strictly following the law. There are plenty of PIs who are willing to bend the law.