SQLCMD: "Login failed for user" on SQL Azure, but it works with SSMS
The error was some encoding issue with Powershell. I suppose the password's special characters were not read correctly by Powershell.

In cmd.exe, it worked flawlessly.