Your recipients do not have their email clients properly configured to convert Quoted-Printable MIME messages. That character is the correct MIME character for a blank when Quoted Printable MIME encoding is sent.
Your gateway should not be doing anything with MIME going out. MIME is necessary for non-ASCII data to pass through your gateway.
See RFC2045 (section 6.7) at
ftp://ftp.rfc-editor.org/in-notes/rfc2045.txt
for details.