Well, I was thinking that maybe it could have a little database of md5 checksums. That way it would only have to get the md5 for the picture in question, and then compare it to the md5 database. Of course, this would still require that the script scan the entire gallery in order to make the database, but you'd only need to do that once obviously.
Maybe you could even go so far as to divide the database up into sections. Like, if the first character of a picture's md5 checksum is '4', then the script only scans the section of the database that has md5 checksums that begin with '4'. This way, it only has to scan maybe a few hundred numbers for a match instead of the entire database of 2000+ (in my gallery's case). It seems to me that this would greatly reduce how resource-consuming this duplicate checker would be.
Anyways, just tossing ideas out there for anyone that wants to try coding this.
Edit: Also, another idea. Maybe instead of md5 checksums, a method of looking at colors can be used. Possibly something like a database of what color (rgb value) is used the most in each picture. And maybe have a small margin of error for the rgb values (like + or - 5 in the red value, the green value, and the blue value), since color can be lost due to compression. If this method is used, it would be much more powerful than simply checking md5's since the resolution, filesize, and other such things wouldn't matter. And I don't think it would be too much more resource-consuming than checking md5's as long as a database is used. Again, just an idea. I'm not a web-developer in any way, shape, or form.