I have an update.
As time went on, the number of URLs without insertions has decreased. The pattern of change was weird though:
1. First, some insertions began to work, in order of appearance, from left to right. For example, we started to receive clicks where URL had {keyword} insertion, thought {adID} and {MatchType} would still be in failing and URL would contain %7BAdID%7B and %7BMatchType%7B
2. Then adID insertion began to work
3. MatchType insertion is working now again.
Buf if {keyword} insertion did not work, then the rest of insertions did not work either.
Now only relatively small portion of traffic had corrupted/failed insertions.
I'd like MSN to escalate this issue and fix it ASAP.
Maxim