Sounds like it's being sync'd with something - do you have some sort of cloud photo storage service that you need to delete the photo from in order to truly get rid of it?
If not, then the only thing I can think is that it's whatever you're using to delete the pictures. Have you tried a file manager? I use a free one called File Manager (available on the Play Store) which has the advantage of showing (tiny) thumbnails so you can see what you're trying to delete. It also has a search function in case you're having trouble tracking down pictures (usually, they're in Internal Storage under /DCIM/camera).
