Isn't some of this govered by other regulations as well?
I recall reading (ironically in recruitment literature for the Metropolitan Police, some two decades ago) that records of minor offences commited under the age of 18 were either wiped or sealed in some way so as to give people reaching the age of majority a clean sheet with the chance to start afresh. Surely there is legislation other than the Data Protection Act as well that applies here (and in similar cases) that the police should also be obeying?
There recently was a report in the press about a man refused registration at a dentists as he was a non-attender for an appointment over a decade previously when he was aged 12. Perhaps if a few public bodies and businesses were properly penalised for holding inappropriate data, things might improve.
The best penalty would be for them to be denied permission to run any kind of electronic data systems for 12 months, that would get their attention.