This is probably caused by something else, because SpamSieve doesn’t have any interaction with Mail’s search function, and we’ve never had any other reports of search problems related to SpamSieve. However, to troubleshoot this you could:
See whether disabling the SpamSieve plug-in in Mail’s “Manage Plug-ins” sheet makes a difference.
Describe in more detail what the search problem is (i.e. what you did, what happened, and what you expected to happen instead).