I'm a little bit confused because you handwave the issue in paragraph one by calling it "the testimony problem", and then seem to build on that to refer to alignment spells as epistemic truth in paragraph two.
They're two distinct issues.
The question of whether the cleric or paladin who tells the king that he is evil is lying, or not, is a question about testimony. It can be overcome by having the king cast the spell himself, in a self-scan.
I often see the testimony issue presented as a usable wedge, for gameplay purposes, between alignment truths and NPC self-conceptions. But the relatively easy possibility of self-scanning (especially by demons and devils, who in many editions have their own alignment-detecting magic) means that the wedge is pretty thin.
The deep source of tension is that, in the real world, we have direct epistemic access to facts of value only via our epistemic access to the non-value facts on which they supervene; but D&D posits that facts of value can be known directly and immediately (metagame, via plonking down an alignment label; ingame, via using magic to read that alignment label), without the facts on which they supervene being known.
To give a simple example, in real life the question of whether someone is or isn't "irredeemably evil" supervenes upon such facts as their disposition (if any) to be brutal to others. The question can't be answered without forming a view about this (and many other) salient facts about their actions and dispositions.
Whereas in D&D, the game posits that I can write "chaotic evil" on an NPC's character sheet, without committing myself in any detail to what exactly that NPC's behaviour and dispositions will be. In a game in which moral evaluation is not to the fore, and characterisations are expected to be pretty broad-brush, that's fairly harmless: if I need to know more about the personality of Grugnur, the frost giant Jarl of G2, I can just extrapolate from fairy tales and legends about brutish giants, ogres and the like: let's say he is greedy, cruel and likes to suck the marrow out of the bones of his captives!
But in some moods (eg Planescape; or intentionally subtle political or character-focused play), D&D first writes down alignment labels, but then treats it as a further, open question what exactly that NPC's behaviour and dispositions will be. This is where the potential for incoherence between immediately posited values, and the non-value facts on which such value actually intervenes, arises.
If I have the right personality for it, I can commit mass murder of thousands in order to perhaps save the human race from utter destruction[1], and if my Robe of the Good Archmagi ceases to function, who cares? It's just an object, and it's less important than my mission. [Or at least, that's one way a given character might view the situation.]
The game posits an unmediated access to consistent effects, which get labelled as "good" and "evil" in the metagame--but there's no need for a PC or even a player to accept that label.
The idea that "good" and "evil" are purely metagame labels is a contentious interpretation in every edition of the game prior to 5e, and I suspect would be regarded as contentious by plenty of 5e players too.
For instance, the outer planes (in the standard AD&D PHB appendix 1 cosmology) are aligned, and known to be so by those who live in the gameworld.
In pre-4e editions, spells like "Detect Evil" and "Know Alignment" provide ingame information using the language of alignment. I guess a character could argue that "the cosmos" got it wrong, but it's not exactly clear what that would even mean - eg if the Abyss is not necessarily
evil, then what property is the Detect Evil spell detecting? The property of
being disliked and repudiated by the cosmos? From the point of view both of metaphysics of morals,
and of gameplay, if you want to create the conceptual space for individual's to make their own moral judgements, I think it's easier just to drop alignment as a part of the gameworld.
If this path is taken, alignment might still be a useful personality shorthand in monster statblocks, which is roughly how 4e treats it, and perhaps how 5e tends to treat it (with the odd exception). But then you don't need to say that the Abyss and its inhabitants are
irredeemably evil. It's enough to say that the Abyss is a violent and unpleasant place whose inhabitants are prone to vicious displays of cruelty and destruction. To pick up on [MENTION=2067]Kamikaze Midget[/MENTION]'s example, if the PCs then meet a demon who seems not to be prone to such displays, they (and their players) can form their own moral judgements.