It looks like you're new here. If you want to get involved, click one of these buttons!
Another good way to index your tables when you have an existing system like this is to turn on query logging, let it run for awhile, then look at the most frequent queries. Now place indexes on the columns you search on (where w=x and y=z). If you do a lot of searching on tables that become large, this can help tremendously.
Way too many variables to even speculate why this would be happening on a particular install.