So it isn't a case-sensitivity issue -- that makes sense because if that were happening due to client software (Outlook) it would be breaking way more than Marketo links!
About CNAMEs and branding domains:
Only one branding domain can be valid at a time (unlike landing page domains, you can't have domain aliases, you get only one).
If you have a private DNS server that contains a manually-managed copy of your public DNS zone, this can cause confusion similar to what you describe. For example, hampleman.com's public DNS record (which the rest of the world uses) might have click.hampleman.com's CNAME set up incorrectly, or not set up at all. But if inside hampleman.com's headquarters there's another DNS server with a copy of the zone, and that zone is set up correctly, then internal users -- using the internal DNS server -- will say, "Works for me" while your leads will say, with equal certainty, "It's broken." This kind of setup is called split DNS. It's almost always a bad idea unless it can be justified for security reasons. I don't know if your company uses it, but if so your IT staff needs to be acutely aware of the possible problems it can cause, and must learn to mistrust internal users' testimony about external DNS issues.
Another situation can be broken DNS replication. This happens when some public DNS servers have the right data, and some have the wrong data, and they are not properly communicating to both use the latest, synchronized records.
Still another DNS-related cause can be very long TTL (expiry time) on a bad DNS record, like 7 days or 30 days. If you set a TTL like this, then you realize you mistyped something, you're going to have some people who see the old, bad record for a very long time, while newcomers will only see the new, fixed record. Any TTL beyond a day can get kind of hairy for this reason.
.png)