It's my understanding that themes that haven't been updated in two years don't appear in search results. Many of these old themes won't have the tag anyway. Additionally, there are themes without the tag that are responsive.

As for requiring all themes to be responsive, I could see that happening in the future as our automated tools get better.