Nametags can not be found via fishing or dungeon loot

Nametags are unable to be obtained from fishing or from any generated structure chests. Many hours of fishing and thousands of blocks explored have not yielded a single name tag. Please note as this may be significant, this was conducted on a *realm *hosted world.