Yeah, it's not really a performance issue per se. I have a search that works fine, and then when I add some additional criteria (that reduces the number of records to be returned) it completely borks the search and times out. NetSuite is claiming that adding text fields to the criteria is what is doing this, but if their process works the way I've been led to believe, this is a defect, not standard behavior.