Supplemental address should be searchable
It does sound like a reasonable feature request, and the good news is that it's already been implemented. 

The pull request was merged in March, so any version of CiviCRM from 4.7.18 upwards should include it in the advanced search criteria.

I checked locally and here's a screenshot of the changed address fields in advanced search: