How to speed up search results on a bigger store?

Hi,
I have 1.4.9.1 installed and have appr. 600 categories and 3000 + products.

When doing a search (with or without including the product descriptions), it takes appr. +/- 25 seconds before the search results are shown.

I have installed vQmod and the db_speed_clause_shift.xml

What can be done to increase the spead?

My site is on a Virtau Private Server.

Thanks :-)