Thanks for the insight, that's very helpful. That would confirm what I suspected: it's not the core solving algorithm that's slow. Rather what's slow is building the graph in the first place.
Yes, I had overlooked that Go probably doesn't have anything like the crates.io index (https://github.com/rust-lang/crates.io-index) to allow instant discovery of versioning metadata. And, AFAICT, even MVS would have the same problem here and would take the same time to resolve, since it still needs to access the network to fetch remote repos to discover versioning metadata; rather than pointing the finger at SAT solvers, it looks like vgo should be tackling Go's lack of a central package host (the vgo manifesto mentions "proxies", but it seems that those are just intended for solving the problem of persistent availability).