I've checked obvious things like the template, switching off SEF URLs, disabling some of the search fields in case it was just one of them which was causing the problem, looking for script errors but regardless I just keep getting the same "no results" ... result

You can view the page at http://www.youngacademyofscotland.org.uk/members/membership/yas-members.html to test the search and I can give you backend access if needed, or if you have any pointers then I can investigate myself.