Have you guys seen this thread:
http://www.phpdig.net/forum/showthread.php?t=978 ? It speeds up search queries quite a bit. With 1.8.7 though it doesn't seem to recognize the different types of queries, except for start and exact. Basically it gives the searching job to the MySQL DB, which can perform the functions faster than PHP. I'd be curious how much of a difference it would make for you, JM, since you have so many pages indexed