Скорее всего, содержимое сообщения кодируется с использованием BASE64 или Quoted-Printable.
Вам необходимо проверить заголовок Content-Transfer-Encoding.
Вы можете использовать метод Convert.FromBase64String (string s) для декодирования BASE64.
... или вы можете использовать коммерческий компонент, так как MIME сложно.