Serch places only works within the ESTATE you are currently in.
You have to understand what an estate is:
The Mainland is ONE ESTATE
A private island can be an estate of its own or be part of a larger estate with other private islands, typicall of one owner.
SO.....If you do a search on an island, you only get responses for the estate that island is in.
THE BIG PROBLEM - If you are on the mainland and do a search you will get a ton of entries, BUT none of them will be on private islands. THIS IS A BIG PROBLEM.
This also affect the 'All' search, since 'All' pulls from the 'Places' search.
I have Bug reported this as well as discussed it with a Linden. I encourage all island owners to test this for themselves and report it as well.
To Linden Labs: Are you aware of this and is it going to be corrected and when?