VIM uses wrong encoding – but only in status messages

I ran into a strange issue with my ArchLinux setup. Vim uses correct encoding for reading/displaying files but these status messages (which displays the current mode or reports back when the buffer is written to a file) uses a wrong encoding for the (Hungarian) message.

I tried to set termencoding=utf-8 but it does not solve the issue. The encoding is correctly set to utf-8. The MATE Terminal is also in UTF-8 and my locale is also in UTF-8:

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

I currently ran out of ideas, please help me out.