There's something about pasting vs typing that fails to give the user the necessary feedback and this has been a problem for a while. I faced this same issue years ago and I finally figured out my passwords were being truncated by hitting the 'forgot password' link and noting that the service emailed me the plaintext password (another problem but let's do one at a time) which was fewer characters. My original was 32 and the one they sent was far fewer.

I emailed support to ask and they said 'oh yes, we limit the number of characters in your password'. There was no documentation or feedback on the page to tell you this if you pasted the password, but if after pasting you deleted the last character and then tried to re-type it, you would see the error. Pasting never triggered the tooltip telling you the issue.

Now I try this each time I sign up for something which is a minor hassle but still much easier than the seemingly random failures I had been seeing. It also taught me to immediately sign out and test the services' password recovery functionality to weed out the ones storing plaintext passwords, so that's good.