I don't know about the languages that Montaigne was thinking of, but the claim that some languages lack a word for lying is one that has continued to crop up. A few months ago Steven Point, who is currently the Lieutenant Governor of British Columbia, asserted that there is no word for "lying" in his language, Halkomelem. It appears, however, that he is mistaken: my sources say that in his language smétnqən means "to lie, speak falsely" and that q̓íq̓əl̓stéxʷ means "to lie, deceive".
An earlier example of the same theme is due to no other than John Wayne, who in the classic western Hondo asserts that "The Apaches have no word for 'lie'." That is sort of true: the Western Apache dictionary that I own lists not one but two different expressions for lying. There is a verb meaning specifically "to lie", e.g. ɬeíɬchoo "he lies", as well as an expression meaning "to lie, deceive", e.g. bich'ii' nashch'aa "I lie to him".
It may well be true that these cultures have a particularly negative view of lying, but tall tales about the lack of a word for it aren't a good way of making this point.