Using custom fields to store secondary addresses
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. 

I tested searching for a non-primary "personal" address and the results showed the contact.

It might be something that could be made clearer, because I found a similar thread on it here.