But I just had a thought on this. Instead of the name tags being player created, how about they can only be bought from a villager? Like a blacksmith? If you come across a village with a blacksmith, or you could make a smithing table and place it in the village so one of the villagers becomes a blacksmith, they could make the name tags and trade them to you for emeralds or some other tradable item. How about that? Name tags should definitely be easier to aquire than just finding them in dungeon chests. Maybe change them so they can only be placed on tameable creatures? That way it eliminates the possibility of lagging the server by having too many mobs spawned.
I love how dungeons are described as "extremely rare" when they are the most common structure in the game - really; just considering the biomes that villages or most other surface structures can generate in they are a couple dozen times more common - you just have to do half the name of the game to find them (IMO, WAY too many players don't even give mining a second thought and just want to make autofarms and craft everything, some even want autocrafters):
I've mined over 3,000 mob spawners in the same world (I modded the game to display them in the stats, vanilla doesn't list them for whatever reason) - making them about 50% more common than emerald ore but found in any biome; to get an idea of the amount of caving needed to find one I crafted an average of 209 torches per spawner (this does include cave spider spawners in mineshafts, which are about half the total):
These are all the spawners I found in a modded world (I made it so you can use Silk Touch to get the spawner cage as a decorative block); I found most of them in 121 play sessions and 466 hours spent caving, or more than 3 per session, and about one per hour (they also added name tags to additional structures since 1.6, the version this thread was started in, offsetting an increase in the rarity of dungeons, which are still far more common than any other structure, aside from in oceans as I doubt dungeons can generate in them anymore as they require an air pocket and caves are now flooded):
The same can be said of other items which many players want to be able to craft, like saddles and horse armor - I don't bother collecting more than a few saddles (I would if they were stackable, as otherwise they just waste valuable inventory/ender chest space) or horse armor below diamond (of which I have several double chests of in my first world, where about a quarter of the explored area was generated before 1.6, so I'd have collected about a third more name tags than shown above).
Also, you don't even need to explore anymore already - just go fishing, one of the most OP mechanics in the game (due to auto AFK farms, which should be patched; this can then enable increases in the chance of items like name tags; an easy way to fix this is to make Mending require manually repairing an item in the anvil, much like you had to with renamed items before 1.8, and make Luck of the Sea be required to obtain any treasure, but at a higher rate than it currently gives to offset the lack of treasure from unenchanted rods). You can also now get them from trading; overall, they are easier to obtain, and renewable, than they used to be, making a crafting recipe much less useful: