First, I must admit I only have about 170 Facebook friends to test with.  I'm not popular enough to test the 1000 friend case. :-)  In my case, on a fast internet connection, I did not see any discernable difference in search time.  For more FB contacts or a slow network, I'm sure it would slow down the search, though.

Next, I'm not sure how we get around this if we are not permitted to persist the FB data on the phone.  We have to pay the loading penalty over the network at some point.  At least here we have the search progress spinner so the user has the feedback that this might take some time.  Once its loaded the first time then it gets much faster.

For the non-FB case, however, there should not be much, if any slow down in search.  The only cost here is taking the pre-loaded contact object and rendering the search string.  The string normalization can be costly during load when the CPU is maxed out, but runs quite quickly here compared to the FB network load.

I guess I'm not sure what the alternative is.  It seems like we say "you can search FB contacts slowly" or continue to just disallow FB searching.