As far as I can tell from various sources on the internet $user\0$user\0$pass (which is authorisation_id, authentication_id, password) is the same as \0$user\0$pass - when the authorisation_id is omitted the server takes the authentication_id for authorisation.

I have never had problems with AUTH-PLAIN in smtp-cli. I dare to say if you experienced any such problems validate that the server is doing the right thing.

What software do you run on the server, by the way?