I'd solve this by warning users who attempt to reuse consumed links that the link has been used already, and likely list broken email providers that I suspect are using software that breaks this. And then wait. Let them complain to their IT, or whomever is responsible for picking broken software.
If I was feeling really petty, the clown that wrote this link scanning software isn't in charge of the networking, so you could eventually enumerate the subnets that MS uses, and black list them. Then the links might actually get to users connecting from non MS data centers.
You could roll over and decrease your security so that MS can claim they increased theirs... But you shouldn't! They can only get away with turning security into a negative sum game if you play along. Please don't?