The log seems to show that emails are being sent, it looks like it's finding the servers to deliver mail to - but they are not getting there.
I started with exim4, but my other server had postfix, so I tried that, the results are similar. In exim, the emails were frozen. Basically not returned undeliverable, but not delivered.
Here is the log when I tried to send 3 emails with a php script - one to a hotmail account, one to gmail account, and another to a company account that's hosted on gmail.
Aug 2 21:59:01 myawesomedomain postfix/pickup[28232]: 9B4C79DEDB: uid=33 from=<www-data>
Aug 2 21:59:01 myawesomedomain postfix/cleanup[28272]: 9B4C79DEDB: message-id=<20160802215901.9B4C79DEDB@myawesomedomain.com>
Aug 2 21:59:01 myawesomedomain postfix/qmgr[27728]: 9B4C79DEDB: from=<www-data@myawesomedomain.com>, size=380, nrcpt=1 (queue active)
Aug 2 21:59:01 myawesomedomain postfix/pickup[28232]: 9E9849DEE7: uid=33 from=<www-data>
Aug 2 21:59:01 myawesomedomain postfix/cleanup[28272]: 9E9849DEE7: message-id=<20160802215901.9E9849DEE7@myawesomedomain.com>
Aug 2 21:59:01 myawesomedomain postfix/qmgr[27728]: 9E9849DEE7: from=<www-data@myawesomedomain.com>, size=378, nrcpt=1 (queue active)
Aug 2 21:59:01 myawesomedomain postfix/pickup[28232]: A1E649DEE8: uid=33 from=<www-data>
Aug 2 21:59:01 myawesomedomain postfix/cleanup[28272]: A1E649DEE8: message-id=<20160802215901.A1E649DEE8@myawesomedomain.com>
Aug 2 21:59:01 myawesomedomain postfix/qmgr[27728]: A1E649DEE8: from=<www-data@myawesomedomain.com>, size=383, nrcpt=1 (queue active)
Aug 2 21:59:01 myawesomedomain postfix/smtp[28278]: connect to gmail-smtp-in.l.google.com[2607:f8b0:400d:c06::1a]:25: Network is unreachable
Aug 2 21:59:01 myawesomedomain postfix/smtp[28282]: connect to aspmx.l.google.com[2607:f8b0:400d:c00::1a]:25: Network is unreachable
Aug 2 21:59:02 myawesomedomain postfix/smtp[28278]: 9E9849DEE7: to=<myexcellentemail@gmail.com>, relay=gmail-smtp-in.l.google.com[209.85.232.27]:25, delay=0.57, delays=0.01/0.01/0.29/0.27, dsn=2.0.0, status=sent (250 2.0.0 OK 1470175142 u184si197895qkh.319 - gsmtp)
Aug 2 21:59:02 myawesomedomain postfix/qmgr[27728]: 9E9849DEE7: removed
Aug 2 21:59:02 myawesomedomain postfix/smtp[28277]: 9B4C79DEDB: to=<myexcellentemail@hotmail.com>, relay=mx1.hotmail.com[65.55.37.104]:25, delay=0.65, delays=0.01/0/0.24/0.39, dsn=2.0.0, status=sent (250 <20160802215901.9B4C79DEDB@myawesomedomain.com> Queued mail for d$
Aug 2 21:59:02 myawesomedomain postfix/qmgr[27728]: 9B4C79DEDB: removed
Aug 2 21:59:02 myawesomedomain postfix/smtp[28282]: A1E649DEE8: to=<companyemailhostedatgmail@mycompanydomain.com>, relay=aspmx.l.google.com[173.194.207.27]:25, delay=0.89, delays=0/0/0.49/0.39, dsn=2.0.0, status=sent (250 2.0.0 OK 1470175142 s37si2836049qta.36 - gsmtp)
Aug 2 21:59:02 myawesomedomain postfix/qmgr[27728]: A1E649DEE8: removed