I talked to a guy that worked on Windows Live about the 16 char restriction. Microsoft Accounts also do not support Unicode, or anything but a small subset of ASCII characters.
First, there must be a maximum size. Obviously, you're not going to allow allow 2^64 byte passwords. So it's under that. But, sure, 16 characters is pretty low.
The actual reason seems to be lost to time. The password code was originally written well over a decade ago, when things were less security focused. For all we know, some part of the auth pipeline (even if the passwords are stored hashed) might have sent the user data in a space or comma delimited, using 8-bit chars without UTF-8 support.
He explained that every time they've reviewed it, the password restrictions haven't been close to the top of things they can spend their time on to improve user safety.
I've run into other companies that limit symbols, citing problems with users on mobile devices messing up and generating support tickets. That sounds reasonable for lower-security assets.
Evernote's space explanation sounds really silly. Why not just include stripping spaces as part of the password "hash" function? That's gotta be easier than using Regex.
I remember reading a story about Facebook, where they flipped-case hashes as well, again to help the user login experience.