I think that your code is only deleting the data from the tables MediaStore.Images.Media tables and not the physical images.
What you can is query the MediaStore.Images.Media.DATA field which gives you the absolute path to the image.
Then delete the file as you would delete a normal file.