We have removed as many rights as possible from users who are not logged in, i.e. we have set them to false for "*" and "user". After that change, setting up a new user or mailing oneself a new password (forgotten password) doesn't work any longer. I had to re-enable
$wgGroupPermissions['*']['editmyprivateinfo'] = true;
to make it work.
I suspect that the login process is in some sort of limbo until the new password is entered where the user is logged in enough to have validated their password, but not logged-in enough to be able to change their password.
All you get is the no-permissions screen, it's not like the change password screen comes up and fails.
I don't know what he full intention of that permission is. If you are not logged in, there should be no "myprivateinfo" that you could edit, so the permission should not be relevant then. And we want our logged in users (which we put into a "legit" group) to be able to change them, so editmyprivateinfo was true for them all along.