S-Matrix in $\mathcal{N}=4$ Super-Yang Mills

As you note the construction of asymptotic states breaks down in a CFT since there is no mass gap. It is therefore necessary to introduce an IR regulator by using, eg, dimensional regularisation. The full scattering amplitude will then depend on this regulator. However, it is possible to construct physical observables that do not depend on the regulator. Furthermore, the amplitude contains subleading terms that also are independent of the regulator, and these will be the same in any regularisation scheme. As an example of this the four particle scattering amplitude takes the form $$ \mathcal{A}_4 = \mathcal{A}_4^{\text{tree}} \exp\big[(\text{IR div.}) + \frac{f(\lambda)}{8} (\log(s/t))^2 + (\text{const}) \big] $$ The coefficient $f(\lambda)$, the cusp anomalous dimension, is independent of the IR regulator and hence universal.

The AdS/CFT dual of a field theory scattering amplitude is the expectation value of a polygonal light-like Wilson loop, see, eg, arxiv:0705.0303, which also contains a bit of discussion about IR divergences and a bunch of useful references.

Type II B string theory on $ AdS_5\times S^5 $ gives, through the AdS/CFT duality, $\mathcal{N}= 4, D=4 $ super yang-mills theory. Therefore, if one derives the S-matrix elements of type II B string theory on $ AdS_5\times S^5 $, then the S-matrix for $\mathcal {N}=4, D=4$ super yang mills arises. At least, that is my way of thinking of it. I suggest you read the paper by Giddings, "Stephen B. Giddings, The boundary S-matrix and the AdS to CFT dictionary, hep-th/9903048".