HTML email gets garbled when received through Exchange Server

We have set up a web application on a clients website, which is a Windows machine running ASP and PHP. When we send HTML-based e-mail through the server's normal mail channels (via our scripting), we receive it fine but it becomes garbled in a really strange way when it is sent to the client. We think this has something to do with their incoming Exchange server setup, but we can't really be more specific when making a recommendation to them as far as a fix.

Here is an e-mail snippet as we receive it:
==================================================
<table width="682" border="0" cellspacing="0" cellpadding="0" align="center">
      <tr>
            <td><img src="http://www.theclient.com/images/emaillayout_one_02.gif" alt="emaillayout_one_02" width="682" height="67"></td>
      </tr>
      <tr>
            <td><img src="http://www.theclient.com/images/emaillayout_one_04.gif" alt="emaillayout_one_05" width="682" height="33"></td>
      </tr>
      <tr>
            <td class="center"><table width="90%" border="0" cellspacing="0" cellpadding="0" align="center">
                        <tr>
                              <td width="350" class="textLeft"><p>Fred,</p>
                                    <p>Thank you for submitting an online support form. You will receive
                                          an email notice when our support team addresses your submission.
                                          You can login to track the status of your support ticket at anytime
                                          by using the link below.</p>
                                    <p><a href="http://www.theclient.com/login.php?uid=fred@fred.com" target="_blank">http://www.theclient.com/login.php</a></p></td>
                              <td valign="top"><table width="225" border="0" cellpadding="0" cellspacing="0" class="tableGrey">
=================================================

Here is the same e-mail snippet as they receive it. Note the extra styling garbage and the fact that there are lots of bizarre character sequences sprinkled everywhere ( the link "http://www.theclient.com/login.php?uid=fred@fred.com" for has become "http://www.theclient.com/login.php?uid=fred@fr=d.com", which is not particularly useful):
=========================================================
<table class=MsoNormalTable border=0 cellspacing=0 cellpadding=0 width=682
 style='width:511.5pt'>
 <tr>
  <td style='padding:0in 0in 0in 0in'>
  <p class=MsoNormal><font size=3 face="Times New Roman"><span
  style='font-size:12.0pt'><img border=0 width=682 height=67 id="_x0000_i1026"
  src="http://www.theclient.com/images/emaillayout_one_02.=if"
  alt="emaillayout_one_02" NOSEND=1><o:p></o:p></span></font></p>
  </td>
 </tr>
 <tr>
  <td style='padding:0in 0in 0in 0in'>
  <p class=MsoNormal><font size=3 face="Times New Roman"><span
  style='font-size:12.0pt'><img border=0 width=682 height=33 id="_x0000_i1027"
  src="http://www.theclient.com/images/emaillayout_one_04.=if"
  alt="emaillayout_one_05" NOSEND=1><o:p></o:p></span></font></p>
  </td>
 </tr>
 <tr>
  <td style='border-top:none;border-left:solid #AE96BF 1.0pt;border-bottom:
  none;border-right:solid #AE96BF 1.0pt;padding:13.6pt 13.6pt 13.6pt 13.6pt'>
  <div align=center>
  <table class=MsoNormalTable border=0 cellspacing=0 cellpadding=0 width="90%"
   style='width:90.0%'>
   <tr>
    <td width=350 style='width:262.5pt;padding:.75pt 10.2pt .75pt .75pt'>
    <p style='line-height:14.25pt'><font size=1 face=Verdana><span
    style='font-size:8.0pt;font-family:Verdana'>Fred,<o:p></o:p></span></font></p>
    <p style='line-height:14.25pt'><font size=1 face=Verdana><span
    style='font-size:8.0pt;font-family:Verdana'>Thank you for submitting an
    online support form. You will receive=20 an email notice when our support
    team addresses your submission. You can login to track the status of your
    support ticket at anytime=20 by using the link below.<o:p></o:p></span></font></p>
    <p style='line-height:14.25pt'><font size=1 face=Verdana><span
    style='font-size:8.0pt;font-family:Verdana'><a
    href="http://www.theclient.com/login.php?uid=fred@fr=d.com"
    target="_blank">http://www.theclient.com/login.ph=</a><o:p></o:p></span></font></p>
    </td>
    <td valign=top style='padding:.75pt .75pt .75pt .75pt'>
    <table class=MsoNormalTable border=1 cellpadding=0 width=225
     style='width:168.75pt;border:solid #CCCCCC 1.0pt;border-bottom:none'>
     <tr>
=========================================

Any ideas what factors could be causing their e-mail to be borked?