I've just read a copy of the letter than anyone who's data has been lost will be receiving on the HMRC website. These paragraphs stuck out for me.
This data includes your and your children’s names and dates of birth, your address, your National Insurance number and, where relevant, the details of the bank or building society account into which your Child Benefit is or was paid.How did HMRC do this? Well, I guess if they have sort codes they can query to sort by them and then extract that data to a file. Then they could manipulate the file to sort and separate into further files containing the data for each individual bank.
If you are paid through a bank or building society, they are aware of this matter. They are acting on this information, and assure us that they have appropriate safeguards in place to protect you.
To be honest, getting the data sorted would be easy. The really big question is how did they get the data to the banks. It wasn't on a CD by courier was it?
Update: Unless of course they simple told every bank. Watch any account that receives any payment from us, which would cover lots of other things too presumably.