"As with all digital records systems, complete removal would require the hardware holding records to be completely sanitised. This is a process that destroys all data held, for example on a server or hard drive, and not just a particular record."
All the average Joe wants is to have his record deleted, but why not put up the straw man of having to physically destroy the entire system in order to delete one record, and then argue that it would be too costly?
I'm not aware of anyone asking for their records to be deleted and a guarantee that the medium it was stored on is also destroyed. If it is held on re-writable media and deleted it will eventually be overwritten anyway which is probably sufficient for this case. If it is on optical disks or other write once media then there is a larger problem. Of course there are backups to deal with but if they are rolling backups they too will be eventually overwritten, unless of course they want to store the contents of every single transaction for ever, rather than an audit that there was a transaction, but why would they want to do that?