To me, the most troubling thing is that they were charging people to remove their account information and did not actually remove it (from what I have read). If this is true, then how is this not blatant fraud?
Chances are you paid the fee and they marked your info as 'deleted' in the database, effectively unpublishing the information. That would explain how the 'deleted' data could still be leaked.