Personal data should be defined as belonging to one or more layers...
LAYER 1. Data required to be stored for reasons of basic business law.
E.g. you can't demand that the information Amazon need about you for their financial records be "deleted"; that'd be illegal as it violates the integrity of their customer sales database. How can they know what their tax liabilities are if a bunch of their invoices and receipts have error messages where the purchaser's details should be?
This is basic business and finance.
LAYER 2. Data that is legally required to be stored for Data Retention laws, but which can be safely hidden from public view. This is data law enforcement offices may need to access. Checks and balances are needed to ensure this privilege is not abused.
This layer is for data that is used to answer questions like: "Was Suspect A _really_ messaging Person B when the murder took place?"
In a society increasingly reliant on IT, we do need _some_ level of data retention, or the police's job becomes effectively impossible.
LAYER 3. Data which should NOT be stored UNLESS specifically sanctioned by a legal mechanism, such as a warrant issued by a judge.
This includes—for example—text messages sent via IM protocols.
There's no justification for having such conversations recorded in perpetuity by a central server: text messages take up very little storage space and, should a user at either end of the conversation desire a permanent record, there's nothing to stop the client software doing the recording itself.
If law enforcement officers really do need to see what two potential suspects are discussing, they should require a warrant to have such conversations 'tapped' and recorded by the central server, just as is already the case with telephones. However, they do not have the right to demand every word you've ever written since you signed up.
A point to note is that, in order to prove Suspect A's alibi—that he was chatting via Skype with Person B at the time the crime took place, for example—it is only necessary to know that Suspect A _was logged into Skype and sending IMs_. It is _not_ necessary to know details about the actual conversation.
Hence the "layers": a telephone company will usually log when a call was placed, to which number, and for how long, but they don't record the conversation itself unless specifically asked to do so by a suitably worded warrant. And even then, they only record conversations for the period _after_ that warrant was issued, until its expiry.
Any new data protection system needs to take all the above layers of data into account. Lumping all personal data under the same label will never be workable.