"Do not use exim" is nonsense.

Here: https://gitlab.com/gitlab-com/www-gitlab-com/blob/master/source/downloads/index.html#L113

It says "do not use Exim to send email from GitLab". I'd say that is worded way too strongly. While the default way of e-mailing from GitLab and Exim are indeed incompatible (leaving in the middle which of the two is doing something wrong), they can easily be made compatible by simply using SMTP instead of invoking sendmail. The following in gitlab.rb suffices to make GitLab work with Exim:

gitlab_rails['gitlab_email_from'] = 'gitlab@host.nl'
gitlab_rails['smtp_enable'] = true
gitlab_ci['smtp_enable'] = true

When using SMTP, the default is to use localhost as the MTA so no other configuration is necessary.