I had a similar problem and found clues looking through other similar topic threads. I did the following:
1) Changed the Search Type to: Combine (Like and Fulltext)
2) Re-indexed the “Catalog Search Index”
(I had a couple in there that said “REINDEX REQUIRED”.)
I clicked the “Reindex” link.
These alone appeared to clear my problem. I can’t say for sure if the Search Type had to be changed, but I think I prefer having a fulltext option.
I have read in other posts that you may also have to clear your cache.