Simple: were they charging people to unpublish the information from being accessed on the website, OR were they promising to delete the data and go back and rem

Simple: were they charging people to unpublish the information from being accessed on the website, OR were they promising to delete the data and go back and remove extant copies of the data from past backups? 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.