That legitimacy is only granted via democracy is a very new concept. Even the coining ancient Greeks had trouble with it, and it definitely did not emerge quickly during the Neolithic revolution when governments were created at all.
I think it’s more like this: Governments the US doesn’t like very much are 'illegitimate' because 'not liberal democracies'; regimes the US does like are 'important allies' or otherwise not talked about.
The whole 'not democratic' thing is more like a type of post-hoc justification for what, to many, looks like blatant imperialism. It would appear it is successful at least some of the time.
As governments get more oppressive and arbitrary in their exercise of power, it becomes harder for them to make credible claims of legitimacy. I'm not saying the Saudi government is legitimate, but it is possible for it to do things that increase or decrease it's relative legitimacy. Increase consultation and individual freedoms? More legitimate. Crack down on peaceful protests or oppress minorities? Less legitimate.
Saudi Arabia does not get called illegitimate, but Cuba does.
Pinochet was 'legitimate'.