FWIW, if you read the literature closely, Kuuk Thaayorre is also mixed. They have words for left and right and
use them to describe relative orientation, notwithstanding the emphasis on cardinal directions. A related language, Guugu Yimithirr, does seem to completely lack use of left and right to describe spatial orientation; it has the words--similar to Kuuk Thaayorre, words identifying left and right hand/arm--but it doesn't extend them figuratively as Kuuk Thaayorre does. (They both extend other body-related orientation terminology, e.g. to describe being ahead or behind something or someone.) However, Guugo Yimithirr seems to heavily rely on hand and body gestures to help establish relative orientation of the subject or object. Reading the literature, I don't think Guugo Yimithirr would be capable of adequately conveying direction and orientation over the telephone.
Alot of the literature also makes hay about these language speakers having preternatural skills at maintaining a cardinal orientation mentally. I don't doubt they're good at it, but I suspect that that skill is something that has only recently become uncommon in the industrialized world. As a kid growing up in the U.S., being able to keep track of cardinal orientation was something I understood as a skill expected of men, and not by tracking the sun or consciously using other obvious markers. It was quite obviously a vestigial gendered skill at that point--noteworthy if you had any proficiency at it--but clearly one within recent memory of male adults. Moreover, AFAIU, there's also research showing that Americans tend to use cardinal directions and navigation more than many European countries, presumably related to our lived geography.
Interestingly, the literature on Guugu Yimithirr says that cardinal orientation accuracy relative to the Earth is much better the further away the described location. For descriptions closer to home (i.e. the central city/village of the group), accuracy was often off by 30+ degrees, seemingly because cardinal orientation is more dominated by familiar local topographic features. Moreover, IIRC, it seems cardinal direction isn't absolute in these languages. Which, at least intuitively, makes alot of sense to me. For example, the Bay Area is askew; when giving directions "north" is closer to north-west (middle peninsula, East Bay) or north-by-north-west (city), but everybody (conscious or not) is very consistent about the rotation and bending.