It means there is a great possibility that the CIA's search violated the separation....

You should not read it as "well have". You should read it in two steps to see how the structure evolves: 1. the CIA's search may have violated the separation... 2. the CIA's search may well have violated the separation ... Then we look up the dictionary. It (Oxford) says, under definition 3, [WITH MODAL] Very probably; in all likelihood: Example: being short of breath may well be the first sign of asthma. Now we understand. The "well" is an adverb that means "very probably" here. It is used with the modal verb "may".

The phrase isn't 'well have' - it's 'may well + infinitive' The CIA's search may well have violated .... This means that it is highly likely that this happened.