Searching in unstored calc fields do take a long time. If its some field that you are searching regularly in, you may want to use a script trigger to store it.
Another option that may speed up searches on unstored fields:
Perform the find in two phases:
Phase 1: enter find mode, enter critieria only in stored/indexed fields, perform the find.
Phase 2: enter find mode, enter any additional criteria needed in unstored fields and select "Constrain found set".
some of these cases use related tables to calculate and the calculation isnt stored
Why don't you search the related fields directly?