送信前に下記のように文字コードを指定してみてください。
message.setText(msg, "ISO-2022-JP");
GAEのJavaMailとj2sdkのバージョンは何でしょう?
バージョンによる未解決バグかもしれません。
AppEngineSDK 1.5.2
JDK 1.7.0
JavaMailのバージョン、というものがあるのでしょうか。 これはわかりませんでした。
送信前に文字コード指定してみましたが、同じ結果でした。。。
まずは送信されたメールの内容をプレーンテキストで確認してみるのが肝要かと存じます。
不要な空白が増えるようにMIMEENCODEされていれば送信側の問題であると決めてよろしいかと存じますが受信側のメイラーが正しくデコーデできていない可能性も排除できません。
最初の回答した方がおっしゃられるようにJavaMailにもバージョンはいろいろありそのときどきでバグがあったことはあったようです。
http://www.sk-jp.com/book/javamail/contents/javamail_ja_prob.html
http://www.atmarkit.co.jp/bbs/phpBB/viewtopic.php?topic=18213&forum=12
http://www.atmarkit.co.jp/bbs/phpBB/viewtopic.php?topic=18213&forum=12
似たような症状が出ているのでこちらが参考になるかと思います。