OK, if some mail is getting through it means that it is possible to send mail, even if the HTML is being lost along the way. ( hope you have Admin email format set to HTML?
Check the headers on the email/newsletter you received - in Outlook, open the email, then file-properties-details-message source. If there is a return path, reply to or a received from or similar with <nobody> listed, you need to try and get 'Emails must send from known domain' working.
If you are using PHP as the mail transport, switch to sendmail -f to see if that works.
You also need to ensure that there is an Emails sent FROM address defined in email options.
Does your hosting co. have any guidelines or recommendations as to the recommended email setup?