without seeing the source, my guess would be that you forgot the initial v prefix, common for janestreet packages due to a version scheme rename some years ago.
It should be bin_prot = v0.16.0 (the initial v is not optional)
that’s a good question but i don’t think there are any satisfying answers at the moment sadly.
The code in charge of explaining why the dependency solver can’t find a solution is quite complex and was already improved quite a bit in ocaml/opam#6106 as part of opam 2.3.0, but it is still pretty confusing in most cases due to the way it currently works.
In your case for example, the reason you get v0.12.0 instead of 0.16.0 is because version numbers are reconstructed using existing packages instead of taken directly from the package definition (for internal historical reasons), so since 0.16.0 doesn’t exist the code will take the closest existing version which is v0.12.0 (since 0.16.0 < v0.12.0 < v0.16.0).
I’m hoping to be able to fix that in the future but i haven’t had the time to work on it since (contributions are always welcome if anyone is interested though)