This would possibly mean MAJOR re-designing, but you could move the entire site onto PHP and MySQL generation... the menus, and footers could all be in your PHP script, but the data that you want to index could be in a MySQL database...
This would mean that searching would be just a simple MySQL query, and you could use mod_rewrite to make nice looking URLs!
Another benefit of this would be that you could create a cool admin centre for your client where they could edit the content and even the menus!
What do you think of this idea? Is it too late to try it now?