The system already supports downloading images by URL, using http://haruhidoujins.yi.org/db-search.php?url=<URL> so it can be used to check any picture with just a link.
I built it using a heavily tweaked version of imgSeek (for faster searching and greatly reduced memory usage) that needs to run as a separate database server. The imgSeek source is GPL, so it shouldn't be a problem to package it as separate server with Danbooru however.
Currently it needs about 100 MB of memory for the Danbooru image set, and takes ~0.25 seconds to find the 16 best matches on my 2.2 GHz Opteron (plus another 0.5+ seconds to find the corresponding MD5s, which could be eliminated if I wasn't lazy). Both memory and CPU usage would scale linearly with the number of images but there's probably still some room for further optimizations.
I don't know if it'd be appropriate to autorun it on image submission, since it IS rather CPU intensive, and it could only run after the image is already uploaded anyway (except for URL submissions). It might be useful for the moderation queue perhaps, but I don't know how that works. Maybe it could be added as a link for each pic to open a new window with the search results.
Tighter integration with Danbooru would have the advantage that the search results could show tags, dimensions, and other information already. Though for the purposes of the moderation queue or whatever I could just add an interface that returns the MD5 of the search results in a parsable form (JSON/XML/whatever).
I guess it's up to the admins/mods to decide if this would be useful or not.