At least part of it is caused by something between your mail server and their device deciding that you're using quoted printable encoding and "fixing" it. That would account for =21
being replaced by !
and for =34
being replaced by 4
. I don't know what triggers this but based on your description I would suspect that something in your outgoing email headers is telling the device it needs to do this. If your URLs always contain =
but are only corrupted some of the time, your headers may be inconsistent. If the URLs only contain =
some of the time and are corrupted every time they do, then the issue is always there but only visible with the right data.
Try your original URLs at the online quoted printable decoder, you'll get exactly the same changes.