I think you’re really putting the kart before the horse here. It’s certainly not true that no legitimate governments existed prior to the 20th century, regardless of what particular phrases may be been invented to describe them during that time. Just like gravity existed long before Newton managed to come up with a sensible description of it. You also almost get to describing the actual reality of the situation, but not quite, which is that a monopoly on violence and a state are the same thing. All states emerged when some group attempted to assert a monopoly over violence, and whether they fail or succeed in becoming a state comes down to their ability to monopolise violence. The status of legitimacy here is entirely subjective, and if it’s called into question, the only way it’s ever falsified is if some other group successfully challenges that monopoly.