I think I found a super simple solution.
The key observations are:
- Each package has a UUID
 - 
isbitstype(UUID)hence a UUID can be used as a type parameter 
So, the idea is to define a “universal entry point function”:
module IndirectImports
    struct IndirectFunction{uuid, name} end
end
which can be used to refer to a function in a package without importing it. An example usage is:
module Upstream
    using UUIDs
    using ..IndirectImports: IndirectFunction
    const upstream_uuid = UUID("332e404b-d707-4859-b48f-328b8b3632c0")
    const fun = IndirectFunction{upstream_uuid, :fun}
end # module
module Downstream
    using UUIDs
    using ..IndirectImports: IndirectFunction
    const upstream_uuid = UUID("332e404b-d707-4859-b48f-328b8b3632c0")
    const fun = IndirectFunction{upstream_uuid, :fun}
    struct DownstreamType end
    fun(::DownstreamType) = "hello from Downstream"
end # module
@show Upstream.fun(Downstream.DownstreamType())
where the Downstream package defines a “function” in the Upstream package without importing the Upstream.
(The fact that IndirectFunction{uuid, name}(...) does not return a IndirectFunction is kind of bad but it’s not like this is forbidden…)
Does it work?  I feel like I’m missing something as this is so simple.  Maybe it is a too much burden on the Julia compiler to manage a possibly huge list of methods for IndirectFunction?  Or maybe not?