Usually shared hosts use throttling, so that only a few PHP processes can be invoked at a short amount of time. I am only guessing though, it can be related to many other things as well – such as memory limit, number of plugins, overall server usage etc..
If you are using a shared hosting plan, then it is very likely a throttling issue.
You can improve these hits, by turning off the live search trigger, and only enable it during the return key press/magnifier icon click.