it would require multipass overwriting of portions of databases, and sections of backups, without disrupting the integrity of the rest of the data
In my last job, exactly this problem came up. We were operating a service for a client, and it had a massive customer database. The client said "How do we delete our customers from the system?". Our f**kwit designers said "You don't, because you never asked for that facility." Of course, the f**kwit designers had never thought to ask if it would be necessary, nor realised that compliance with data protection legislation would make it essential.
So this kicked off a big study, and, yes, one of the findings was that it would be extremely difficult to delete customers without disrupting the integrity of the database. When you have all sorts of links from customers to financial information, to reports, and so on - some of which will identify the customers, but some of which which will merely use customers' data - then you have to be extremely careful not to screw everything up when deleting a customer. No point in complying with data protection legislation if you are now producing false accounting information!
Of course, it would have been easier if deletion had been designed in from the start. There were also other oddities, such as financial legislation requiring maintenance of customer history for x years (where x varies from country to country). Also the paradox that you might need to keep details of a customer, maked with a flag to say that they don't want to be contacted by marketing.
Lots of lovely problems to keep everyone occupied!