Cannot permanently change locale on 16.04 server

What I eventually did is a combination of above techniques

I've first done

dpkg-reconfigure locales

and chosed english, utf8, then:

localedef -i en_US -c -f UTF-8 en_US.UTF-8

Also edited /etc/default/locale to look like:

LANG=en_US.UTF-8
LC_ALL=en_US.UTF-8
LANGUAGE=en_US.UTF-8

And after reboot, when I type locale it now looks like this:

LANG=en_US.UTF-8
LANGUAGE=en_US.UTF-8
LC_CTYPE="en_US.UTF-8"
LC_NUMERIC="en_US.UTF-8"
LC_TIME="en_US.UTF-8"
LC_COLLATE="en_US.UTF-8"
LC_MONETARY="en_US.UTF-8"
LC_MESSAGES="en_US.UTF-8"
LC_PAPER="en_US.UTF-8"
LC_NAME="en_US.UTF-8"
LC_ADDRESS="en_US.UTF-8"
LC_TELEPHONE="en_US.UTF-8"
LC_MEASUREMENT="en_US.UTF-8"
LC_IDENTIFICATION="en_US.UTF-8"
LC_ALL=en_US.UTF-8

And no more warnings...

The answer was indeed PAM-related, as Gunnar Hjalmarsson mentioned in a comment. PAM was disabled via sshd_config, although I honestly do not remember doing so myself.

To summarize: If /etc/default/locale seems being ignored, check if PAM is enabled.

Run the following commands:

locale-gen en_US.UTF-8
dpkg-reconfigure locale
dpkg-reconfigure keyboard-configuration
localedef -i en_US -c -f UTF-8 en_US.UTF-8
reboot
locale