Yes it is very common to only have few or no matches at higher levels.
I recently have been advising someone who got screaming mad (literally) about spending so much money and having no matches.. so the important thing here is patience.
From 2009-late 2014 I personally had 0 matches.. even at Y37. It was 4 months ago I got a Y67 and until yesterday didn't have my first Y111 match at any distance. None of my matches (except those I have tested for immediate family) have the same Surname. As time passes more matches will appear; though you should have an expectation that over time the numbers will still not be ridiculously huge like your Y12 matches (useless). The most matches of the Y111's I manage (~20) is 5 or 6 last I checked.
Looking at the results sets of a couple of people in my kit that fall primarily into the I-M272 or R-M269 Haplogroups.
- Y12 = 119 - 172 pages x 25 of matches
- Y25 = ~20 matches to 12 pages x 25
- Y37 = 5-10 matches
- Y67 = 2-5 matches
- Y111 = 0 - 4
Note: In one extreme case that actually broke ftDNA's classification system (it defaulted to Haplogroup F); I manage a kit that only has 4 pages of Y12, 4 Y25s, 4 Y25, 3 Y67s, and 2 Y111s.
Y111's are also more significantly more expensive and so in addition to the result set getting filtered down from other Y111s.. the result data set for Y111's is smaller than that of Y67s and that smaller than Y37s.. etc.
So basically Y111's are a subset of your Y67 matches, your Y67 matches are a subset of your Y37s, etc. The exception to the subset of results is BigY, which only requires a Y37 and not a Y111 before ordering.. but do to the cost the total number of BigYs I believe are still under 10,000 based on YFulls index numbers being in the 5700 range right now.
There is sometimes a situation where I have encountered in managing other peoples tests where someone will be a Y111 & Y37 match but not show up as a Y67.. and basically this requires a call to ftDNA to have them run a script and it fixes it.
See this part from an infographic I created for a class once to illustrate some of my points both of precision and why you have less results. More precision equals less noise.
My Y37 matches are still at 3 matches outside my immediate family and so I try to encourage them to upgrade their tests to Y111.
On non-paternal events (npe) , on some of my kits spellings are obvious variations; others are not. In my personal case my 3 matches are trying to identify the NPE and which one, if any of the 3, are our original surnames. The more precise the Y test the easier it will be to track down the NPE, but below Y67 it will be very
difficult and below Y37 likely nearly impossible without more granular tests; especially in cultures which more recently adopted consistent paternal surnames (i.e Norway).
Generally it just takes a lot of patience and further testing by additional people.
Important: Upload your results to YSearch.org; this may also give you more results especially at the lower levels. Ancestry.com used to have a Y-48 test that the data but some of it users posted here. FamilyTreeDNA doesn't do transfers of Y results so this is the only way you can see them and attempt to match to them.
Good Reference Faqs:
General YDNA FAQ which has some additional Q&A: https://www.familytreedna.com/learn/user-guide/y-dna-myftdna/y-matches-page/]6