hereと同じ (基本的な) コードを使用して MCRYPT_RIJNDAEL_128 に切り替えると、php mcrypt_decrypt から正しいデータを取得できるようになりました。
たとえば、以下は復号化のリクエストから返されました。
{"messageData":{"identity":"test","msg_id":0,"token":"fakeToken58586"},"messageName":"fetchSavedData_request"}\n\b\b\b\b\b\b\b\b
これはパディングの問題だと思いますが、文字列を正しい長さにパディングしても、ガベージが発生することがあり、通常はパディングが必要な文字列が正しく返されることがあります。
何が起きてる?