To state the obvious, this can't be all the code, there must be code where the data is sent to the server. Why should that necessarily be error free? What about the remote server, is there some convincing evidence that that code is correct?
Since you also encode the key, do you send the key as well? Maybe you appended it wrongly (or just the wrong way) and that gets sent back as additional characters. I notice that the number of additional characters is about what you would expect if you got sent back the base64_decoded cleartext password. But the characters themselves don't look like base64_decoded, so my guess is probably wrong, but might give you a hint in the right direction
PS: AFAIK MIME::Base64 is a very old and well-tested module, the chance to find the bug there are pretty slim
