Install TWEAKUI and see if the SHOW SEARCH ON DESKTOP is unchecked. If so, CHECK IT.
I have Windows 2k SP4. When I click on find from the start button, nothing happens. I have to open My Computer and click the search button to search. This isn't such a problem, but also when I click on "find target" in the properties of a shortcut, nothing happens. I'm hoping that this is just along the lines of me disabling something that I shouldn't have.