Hi 0x0, Russell from Mailgun here. Do you have a self signed certificate by any chance? We typically downgrade a connection if we are presented with a self signed certificate. That might be what you are seeing.
If you drop us an email at support [at] mailgun.com with your domain I can take a look at the specific issue we are having delivering over TLS to your domain.
SSL_accept error from mail-182-5.mailgun.info[23.253.182.5]: 0 warning: TLS library problem: XXX:error:XXX:SSL routines:SSL3_READ_BYTES:sslv3 alert bad certificate:s3_pkt.c:1258:SSL alert number 42:
At least they retry without SSL aftwards, and manage to deliver the emails.