If your search is timing out it would indicate that the query is taking too long to execute. This is likely because of the complexity of the query and the responsiveness of the database.
In PHP you can extend the timeout period for a script with this code:
<?php set_time_limit(number of seconds); ?>
You just need to add in the number of seconds that you would like to allow the script to run.
As for the issue you are getting with incorrect results please explain this a little more. The time that it takes the query to execute should have no impact on the results that are returned.