Turns out that ldd doesn't run the rtld that's defined in the binary - it has a list of rtlds it tries to run against the binary. If I'd read the output more closely I'd have seen:
/lib/ld-linux-x86-64.so.2 => /lib64/ld-linux-x86-64.so.2 (0x00007f0c656cd000)
The toolchain that built the binary set the rtld to a path in /lib, but ldd was reading it out of /lib64.The kernel only uses the built-in path, so we got ENOENT.