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.

