What is freaking is that it may not be an "artificial restriction", but a VARCHAR(16) restriction caused by a plain-text storing.

We certainly all have done this error: you create a database with the table "User" with the password in plain text. So VARCHAR, and humm, a max size... my password is 6 character long, but some user may go to 8, ok to be sure nobody will never complains, let's go for 16 characters. With some luck, your database truncate VARCHAR that are too long into VARCHAR(16) without notifying you. In this case, chance are nobody will notices there is a problem.

I do not thing this is the current explanation for hotmail. But it is funny to see that it looks like a very basic error.

I seriously doubt that this is the case (though I have no visibility into Microsoft account auth). Most likely, there was some poor design choice years ago (such as the one you described) that has been corrected, but the effects its caused haven't been fixed through the codebase. e.g. I would not be surprised if the code contains something like this:

  struct user_auth
  {
    char username[64];
    char pw[16]; // TODO: Allow longer passwords
    //...
  };

  bool authenticate_user(user_auth* ua);

This kind of code would limit passwords to 16 characters, but would be irrelevant to how passwords are currently hashed or stored.