Actually, this affected Panther, and Jaguar before it... perhaps all versions of OS X? For the sake of this experiment, take an (unimportant!) file or folder and put it in the trash. Then press Command-F to do a search, pull the pulldown to "Search in: Everywhere" and do a search for that file or folder. The Finder won't find it. For that matter, it won't find it if you limit the search to Local disks, Home, or Specific Places!
I'm sure there's some UNIX-y explanation for this, but I was raised on Mac, and no explanation is going to be good enough. When I tell the Mac to search "Everywhere," I want it to search "Everywhere," and that means the Trash too!
In the meantime, here's a workaround. Press Command-Shift-G for the Go To Folder dialog and type "~/.Trash." This will take you to the invisible Trash folder. Then press Command-F to do a search and pull the pulldown to "Search in: Specific Places." You can then drag the proxy icon from the top center of the ".Trash" window (or directly from the Finder if you use column view mode) to the upper pane in the "Search in Specific places" window.
And of course, the next time you search, make sure both your hard drive and .Trash folder checkboxes selected.
Mac OS X Hints
http://hints.macworld.com/article.php?story=20031118222401847