Two possibilities:
1. the mail format isn't correct
2. their Notes installation isn't correct
See also
http://www-01.ibm.com/support/docview.wss?uid=swg21421897To tackle the problem, can you ask them to save the HTML-source of both your mail and a correctly received MIME mail, and send that to you, so you can verify the correctness of the formatting?