I'm thinking it must be in the htaccess file, as I just went live, and suddenly if I search for something like "two words" it ends up searching for "two%20words" and obviously I get no results.
Same goes for quotes, etc. Any ideas?
That wasn't entirely it - it was escaping with a %25 and passing it to the search form, causing no results. It was an issue with my htaccess, it's fixed.