Another factor may be simply your network connection - if a single search is taking 10-20 seconds and this *isn't* to do with the server that you're querying, then it looks like there's either a lot of data being transmitted back and forth, or you've got a slow connection. No matter how many threads you fire off, if they're all trying to receive 100K though a single 56K line then you're going to have to wait a while for all the results to come back.
Cheers, Ben.