iTunes appears to have a bug related to importing playlists (i.e., “.m3u” files). If you drag a playlist into iTunes, the music files are added to iTunes but will not show up in the iTunes Library. Consequently, the added files don’t show up in searches or Smart Playlists either. What’s especially confusing is that the imported playlist shows up in the left column with other playlists! And, when selecting the imported playlist, the imported files will display in the right pane and can be played from there. I’m guessing that the drag-and-drop method doesn’t result in the added files being indexed properly by iTunes.
The solution is to import the playlist via the “File » Library » Import Playlist…” menu item. This causes iTunes to index the files properly as it adds them to the Library. That in turn allows other features of iTunes to work correctly for these files.