Your title is confusing as it indicates you suspect the File.exists as the problem. Looking at your code, the fact that deleted images are added to download queue means File.exists works fine at least the first time. Otherwise, you would not even add it to the queue. Now the question is what happens when it is added to queue and downloaded. Check your code to make sure that it added back to the map properly. In your code, something should be added to the download queue only under two conditions: one if nothing in the map and the other is whatever in the map is deleted. So either it is not added back properly or may be a race condition where your File.exists is happening before the download is completed fully and you are adding it back to the queue again.
Good luck.