How about explicitly declaring orphan trait implementations as public (or not) and explicitly importing them (or not). Trait implementations are resolved at the point where a concrete type becomes generic, and the set of available traits can depend on that context.

This isn't exactly trivial, but it avoids coherence problems.