Do you have the device 'synced' to a google or other online account? If so, then the files are probably there as well, so when you delete them on the phone it is getting them from the synced account. Try this...
1. Turn of the 'sync' option.
2. Restart the phone (turn it off and back on).
3. Delete the file(s).
4. Now log into the account you have it synced to (do not turn sync back on yet).
5. Delete these files from the synced account as well.
6. Log out of the account.
7. Turn on your sync again.
Should be good now.