I like the referenced riddle because you can't "fully" solve it, in the sense that you know all the information. You can figure out which path to take (which solves the riddle) but you cannot simultaneously know who lies and who tells the truth, which gives the riddle a bit of an unresolved feel. (I'm assuming it's one yes-no question only.)
Something that has always bothered me with the "one of us tells the truth, the other one lies" conundrums is couldn't you just ask a simple question with a known answer to check who's who? Something like "what's 1+1" or even a logic question like "if A is true and B is true, is the condition of A AND B true or false?"
Either of their proposed questions should still immediately tell you which door is which, though.
What would be really fun is determining which door tells the truth, then coming back periodically and asking it questions about how the setting's metaphysics work, or where an important NPC is at the moment, or what the BBEG's weakness is.
Yes, that would let you know if the one you asked tells the truth or lies. But IIRC those riddles are usually constructed such that that is not enough to solve them. For example, sometimes there are more than two people that you need to identify. Or you need to find the correct door amongst multiple. All with a single question to one of the people.
Perhaps they both lie, whenever it is convenient for them, including lying about lying, but also about not lying? :-P
And if they upgrade to the Premium package (by becoming politicians), they gain the talent allowing them to lie without ever managing to say anything at all... even while using very many words to obfuscate that fact.:-D