Fix non-deterministic <:< for deeply nested types

Details in the commit messages.

Review by @adriaanm, /cc @szeiger