I finally figured out what was the problem. The two devices used different Android versions with incompatible C++ compiler flags. After updating both devices to exactly the same version the problem disappeared.
While it's not possible to compile a single portable binary using private Android APIs it's possible to compile separate binary for each major Android version and ship them with an app. I described this solution in more details on my blog.