It would be easier to say if you could give some more data (inventory size, visitors, machine), but here is a possibility:

- we use `Sonassi_Fastsearchindex` Extension for Catalog Search index. Although it just indexes title, description and sku (I think I have noticed), it works great and reduces catalogsearch indexer time.
- there will most likely be some indexers that you don't have to run, i.e. for tags or for product attributes. It is sometimes enough if you do only price, product flat, category products and catalogsearch regularly, and the others maybe daily.
- we synchronize products with an external system every two hours, and in the meantime, we index with php-scripts. So, we have a cronjob for each indexer we want to run to a certain time, and let this cron execute the script. This appears to be the best middleway between what the server can do and up-to-date product data.

This is running on Magento CE 1.7.0.2; still a pain, though ;)