Environment:
Linux 4.9.0-8-amd64 #1 SMP Debian 4.9.110-3+deb9u6 (2018-10-08) x86_64 GNU/Linux
MariaDB Version 10.1.26-MariaDB-0+deb9u1

Steps to reproduce:
1. Install a fresh MariaDB system (or use an existing)
2. Import the dump (or the binary file) I have provided in the attachment. Actually, you only need the "user" table. Everything else can stay unchanged.
3. Run flush privileges
4. Try to login as "affiliflex@localhost"

Expected result: (happens to all other non-existing users)
mysqli_real_connect(): (HY000/1045): Access denied for user 'affiliflex'@'localhost' (using password: YES)

Actual result: (happens only for the non-existing user "affiliflex")
mysqli_real_connect(): (HY000/1275): Server is running in --secure-auth mode, but 'affiliflex'@'localhost' has a password in the old format; please change the password to the new format

Notes:

1. The message comes from the mysql_native_password plugin.

2. It only works with this exact data and with this non-existing user "affiliflex". (Any other user will result in the normal "access denied" message) If you add or remove any single row in the users table, the bug disappears. If you change the length of any other username in the table, the bug disappears too. If you change the password of the user "1234567890" to a secure password, the bug disappears too. I think there is some kind of hash conflict, since it only works with this specific data.

3. I could reproduce this bug on three completely different Debian 9 systems. One of these systems was completely installed from scratch, with only MariaDB installed, and nothing else.

4. The root password is "hello", just in case you need it