new feature? - all addresses needs to be searchable
In the advanced search under the "Address Fields" you can choose "Address Location" which defaults to primary only. By selecting all of them you can search by any address type.  answer taken from this thread Using custom fields to store secondary addresses