I think if a person is taking formal lessons then the instructor should have formal qualifications. We already have formalised things like syllubuses why shouldn't the teachers be qualified against the syllabus? Just makes plain sense to me.
To get away from having any one organization in charge of testing, perhaps the testing requirement could be with any organization that is a member of NDCA? The NDCA would have to ensure that each testing organization was held to the same level of difficulty, but that could be accomplished.
I would still worry about rural populations, though. Without a large enough population base no "qualified" teacher could work there, leaving large areas of the country without and dance teachers at all.
And to go back to the club dances, would those teachers need to be licensed as well? A licensed Swing or Salsa teacher? Given that those dances are so fluid, what would be the criteria?