The people who make TinEye have a product called PixMatch which can search individual collections. It's not implemented as a desktop application, though — it's a server-based API. And it appears to be priced for serious enterprise use, not for individuals. So that's there, but not really an answer.

But a competing company does have something for the desktop — Imense Desktop Similar Image Search, which runs on Apple Mac OS or Microsoft Windows with Adobe Bridge CS4. It's free for collections of up to 4000, and seems reasonably priced above that.

There are, in fact, a ton of things, once I figured out what to search for: Content-based image retrieval. There is actually a lot of work in this area, and a ton of both open source and closed tools. Most of these are focused on the big-enterprise/academia side of things, and are in various states of completion and polish.

Of these, I think imgSeek is the most interesting for the desktop case. This is Python/QT-based and so in theory should run on pretty much any platform, but is focused on Linux. It does a comparisons based on metadata (date, time, etc.), simple features like average luminosity or color, or by sophisticated wavelet-based estimation of similarity. That's probably overkill for finding the exact same image in a different size with different compression, but should work really well since that's basically the easiest possible case. It'll also find near matches, like this:

All that may be too much work for this specific one-time problem. How are your not-organized photos stored? Even if their filenames aren't helpul, the EXIF metadata should still be good. One simple approach is to import them into a program which can examine this data and search or sort by it. Or, you could use a program like jhead to rename them all so they have sensible date-based names. (Maybe both.)