First off, a word about your usage of "tier".
If you think of tiers of adventure (where level 5-10 heroes form tier II and so on), this doesn't really work for NPCs. I would suggest using Hit Dice instead, as a more useful measure of a NPC.
add 5 to that DC if the search is conducted in a settlement with fewer than 10,000 inhabitants.
I would have thought the smaller the town, the easier it is to find someone.
Put otherwise, you're conflating the ease of the search with the probability of having somebody to be found. I would not recommend that.
I understand you set a higher DC to lower the probability of there being somebody to find, but this is really independent of how easy or hard it is to find that somebody, if indeed there is somebody.
This all comes to the fore in your example of an Epic PC:
So if my town has 6700 inhabitants I know immediately that there could be about 67 tier 1 NPCs and 6-7 tier 2, and probably no more than 1 tier 3. If my PCs need to find that one tier 3, they'll have a DC 20 check to make. It's nearly impossible to find an Epic level NPC in such a town. If I decided to allow my PCs to try to track one down, that would be a DC of 30.
No, I would say that in a city with 6700 people, any Epic level NPCs are known to every single one of the other 6699 inhabitants.
Unless the Epic NPC doesn't want to be found, in which case nobody knows he's there, and the search is impossible (without Legend Lore type of magic).
Anyway, the existence of an Epic NPC needs to be decided separately from the search to find him or her.
I would never recommend leaving it up to chance for Epic NPCs. You system works best for tier I NPCs, and just possibly for tier II ones.
The D&D 5e game simply isn't made for having random high-level NPCs, so I would recommend against using it for people above, say, CR 5.
Which neatly ties back to what I said earlier about Hit Dice.
NPCs appropriate for Tier 1 adventurers are seldom higher than CR 1. On the other hand, they might have 1-4 Hit Dice. An
Acolyte or
Scout, say. Just like tier I heroes, they're fledgling and hopeful, but not yet in any real position. During this tier, NPCs can actually surpass PCs in ability and survivability. That's okay.
NPCs appropriate for Tier 2 adventurers are seldom higher than CR 2. On the other hand, they might have 5-9 Hit Dice. A
Priest, say. The
Veteran is a top of the line Tier II NPC at CR 3. Read the description of the tier and you'll see how somebody like a Veteran is at this tier. As soon as a player character enters Tier 2 at 5th level, he will always be noticeably more capable than any comparable NPC.
Above I drew the line at roughly CR 5. This is because it still allows "powerful" NPCs such as the
Mage or
Gladiator. They come across as heroes - "name" characters, or Very Important Persons, and so they're tier III. That they compare badly to tier III player characters in a combat is an intentional feature of 5th edition, one which I recommend you do not treat like a bug.
NPCs like
Archmage and
Champion are
definitely tier IV material, even though their actual ability is probably not even half that of the characters in most regards.
Good luck!