I agree there are some Constitutional issues, but I think not fatal ones. It would certainly not be possible to agree to an arrangement where e.g. a U.S. Suprem

I agree there are some Constitutional issues, but I think not fatal ones. It would certainly not be possible to agree to an arrangement where e.g. a U.S. Supreme Court case could be appealed to the ICJ. But it would probably be possible to agree to an extradition agreement, by which an American court, following procedures passed by Congress, could extradite someone under its jurisdiction to the ICJ (there are already many extradition agreements with specific sovereign countries, which might be a constitutionally-significant difference, but might not). The case you link (Medellin) didn't hold that anything was unconstitutional: it simply held that the treaty the U.S. had signed in that case hadn't been implemented by Congress yet, so had no force of domestic law, and couldn't acquire such force of its own accord. They didn't hold that Congress couldn't pass implementing legislation, just that it hadn't.