You have some valid points, tho I wonder if some of the issue lies with the mysql setup. I have a client with nearly 40k members and nearly 1.2million posts. When I type in anything in the drop-down search box results are almost instantaneous. He's running a pretty beefy server, but possibly your mysql needs to be tuned a bit to help with these search times.
