I find it odd that they aren't just able to get the data from the carriers. The only reason it'd be on the device but not the carrier/Facebook/Twitter/etc servers is if they encrypted the messages, but they would probably mention this if it were the case.