My guess is that because your issue just began happening out of nowhere in June, is that your search method setting was changed.
Control Panel > Features > Search > Search Method To Use
select: "UBB.threads Internal"
It is possible that some shared host server configurations do not support "SQL Full-Text"
