The search algorithm is lacking. A search for "Battle Pet" did not find Better Battle Pet Tooltip. The old webpage did.
Your search algorithm needs to be "includes" the entered words not "starts with" the entered words. For that matter, I'm pretty sure the old search wasn't just of the addons' titles but some of the other fields as well. Keywords, maybe?
After further searching for addons, I'm thinking this is not a problem with the Search algorithm but a fallout of the "one page only" issue with there being no Next/Previous buttons to look at more that the first 20 hits resulting from a search.
OK, further searching for addons reveals that the search does indeed find things with only some of the words entered for search criteria (i.e., uses "includes"), but it does not seem to be consistent.