After some digging, the root of the problem is indeed that expand-deps always enqueues all children of every examined dep. The trick is to ensure that we examine every unique dep (tuple of lib and coordinate) exactly once. The goal is to collect all coordinates for a given lib so constraints can be solved consistently, without re-visiting the same coordinates over and over again as showed in my logs. Visiting any given coordinate exactly once also breaks the infinite loop reported by @gavin.
The attached patch 000-canonicalized-deps-once.patch reworks expand-deps to do exactly this. It re-orders the determination of the coordinate to be used for any given dep, so that deps are only ever enqueued with their use-coords. This enables expansion to deduplicate deps.
With the attached patch applied, my use case sees libraries resolved only once, and @gavin's repro expands rather than locking up.