There are a few different phenomena that are easy to conflate here and which may or may not impact the perception of "legitimacy."
Lineage and Certification
One are claims of lineage. A lot of martial arts, especially eastern ones, have a variety of extraordinary claims about their lineage that are a) largely irrelevant and b) pretty grandiose. Frequently conflated with cultural meaning and conflicts that people in the United States are usually only vaguely aware of (e.g., it used to be said that the founder of Hapkido "lived in the mountains" and came down after World War II, partly to avoid saying that he had actually been in Japan).
Related to that is the matter of registration and certification. Sometimes the registering organization can give you an indication, but I've known some very good instructors who have no (advertised) official affiliations along these lines, or who have certifications that it is very difficult to confirm (e.g., it requires being able to speak Korean to actually confirm what they are saying). The latter is a solvable problem to some extent, but not a trivial one. On the other hand, I've known some very bad instructors who have a long list of things posted on their wall.
For example: You'd find no certifying organization for my rapier school beyond that they met a certain minimum of safety standards, but they were still quite excellent and dedicated to the art, and had some great students.
For a movie reference, compare the characters of Mr. Han and Master Li in the 2010 edition of the Karate (Kung Fu) Kid (or John Kreese and Mr. Miyagi in the original).
Another item you'll come across is that many martial arts schools have a tendency to try and talk themselves up relative to their competitors. Practitioners will frequently make claims that just aren't true, or the differences may be true but it is debatable whether the form is superior–or even significantly different–on the basis of those claims.
How much this matters to you is, well, up to you and it also depends on what you are looking for as well as what you personally believe. In many cases in the United States, at least, these are now toned down or not made with the same force that they used to be, but you'll still find remnants of these claims drifting around. You'll also still find plenty of talk about concepts that are not well demonstrated by evidence-based scientific process. This, again, mostly depends on you to the extent that you will want to worry about it. Some very good martial arts instructors still have some claims built-in to their arts in these regards and it doesn't really detract significantly. In other cases it can be a significant hinderance to learning what works or doesn't from a martial art.
As a general rule, many martial arts are "effective." The question is "at what," and that depends on your goals more than anything.
How To Tell
While I'd argue that the earlier two categories are frequently conflated with legitimacy, I'd also argue that by themselves it doesn't tell you much one way or the other. These martial arts are going to be–by and large–legal, regardless of whether they are effective. Kim's schools were eventually broken for things relating to false advertising and tax fraud, but it would have been very difficult to ascertain the extent to which the books were cooked just by being in the classroom.
Instead, go talk to the students and the instructor. Watch them work. Don't just listen to their marketing material, but actually have a conversation with them. Look at the conversation in What Martial Art Should I Start With? as a baseline here. See what you have fun with. See if you can find statements about them online (a lack of statements is not necessarily a danger symbol: some of the best instructors I've seen have very little presence, but if people are making lots of negative statements you should at least listen). See if they are the sorts of people you want to hang around with.
Some things to look out for:
- Long running contracts that don't have clean ways out or other options. If they are trying to get you to sign a year long commitment right through the door, be very cautious.
- Not receiving copies of anything you sign.
- Special "promotion deals" to put you on a special "black belt track." 1st dan (black belt) is an arbitrary designation: One school may not have you get there for years, others may get you there within a year, but the rank isn't as important as the student and the school.
- Lots of belt promotions that all cost significant amounts of money, especially if they are shady about them up front (with many organizations your dan ranks are going to be expensive, but they are also generally years apart, your lower rank tests shouldn't be hugely expensive).
- Claims about the instructor who is teaching you that defy reason.
- Instructors who have stopped practicing.
- Instructors who are abusive.
- Students who treat their particular school of Vastly Superior™ to everything else ever or who seem to deify the instructor.
- Students who are cruel.
At the end, the most important questions are: "Can I learn here?" and "Is this what I want to be doing?" Even an art that is not run very well may still be effective for you, while one that is run extremely well you may just not click with for one reason or another.