Why is overriding the LANG environment variable not changing the language for me?
Because LANGUAGE, which takes precedence over LANG, is set and unchanged.
$ LANGUAGE=nl ls /nonexistent
ls: kan geen toegang krijgen tot /nonexistent: Bestand of map bestaat niet
More info is in the GNU gettext documentation:
GNU gettext gives preference to LANGUAGE over LC_ALL and LANG for the purpose of message handling, but you still need to have LANG (or LC_ALL) set to the primary language; this is required by other parts of the system libraries.