.... Our firm deals with this problem on a daily basis. We have a lot of angry clients, and can certainly relate to your frustration. I'm shocked that this isn't a higher priority issue for SS NZ.
It is a high priority for us as well UncleCheese thats why a team of devs here in SS NZ created the Sphinx module. For most of our clients now we are deploying sphinx based engines for searching. The good thing with sphinx is it works on most shared hosting so we're trying to remove as many barriers to entry as possible. It won't replace the internal search - which could be improved dramatically but AFAIK they decided on sphinx as to not reinvent the wheel considering that gives us so much more functionality.