As far as the original search, I find that searching any related tables is unnecessarily slow. It seems to search all records and then push through to the current table.
What I do to speed it up - especially when constraining from a smaller set of records - is to create an unstored calc field in the table you're searching in. The calc would get the contents of the field you want to search for in the relationship.
So if you're in TABLE_A, and you're constraining using TABLE_B::STATUS, create a new field in TABLE_A called STATUS_CALC, and then formula is TABLE_B::STATUS (unstored). Now perform your constrain on TABLE_A::STATUS_CALC instead.
I've had searches that were taking up to 3 seconds now perform almost instantly.