With BIND I can have an MX record for that. But what about LetsEncrypt ? I can only have a certificate for “example.com” on a single machine. Looks like I’m confronted with an impossible choice.
You can create mail.example.com as an A record with the IP of the mail server. You create an MX record to use mail.example.com. example.com can be the IP for server B, or even www.example.com as well either as A record or CNAME for example.com.
Letsencrypt can create certificates for example.com on both servers. I use letsencrypt with my DNS via Cloudflare, which means I can use the certbot cloudflare plugin to create wildcard certificates, and I even have *.example.com on multiple servers, each server creating their own wildcard. Or for example, mail.example.com letsencrypt on server a, and certs for www.example.com and example.com on server b.
Whilst the email address is contact@example.com the MX doesn’t need to be example.com. It can be anything you like, eg: mail.example.com, mx.example.com.
Letsencrypt supports multiple domain names in certs and even wildcard certs.
Wildcard certs require you to use their DNS-01 challenge instead of the default challenge method with certbot. See their FAQ.
With both variants you can create a single cert for all your services and then simply deploy that single cert to all your servers unsing a renew_hook in certbot.