`cargo update` is non-deterministic + updates unrelated crates (w/ reproduction)

Problem

Hi, I have a small reproduction of cargo update updating the lockfile in a non deterministic way.
It enters some kind of "hysteresis", flipping between two package versions after each call to cargo update.
Also, the packages that are updated are not related to the requested package.

Steps

Even though the reproduction depends on some Windows-only crates, the issue reproduces on Linux as well. (To compile on Linux, use cargo check --target x86_64-pc-windows-gnu after installing the relevant toolchain. To run cargo update zip you don't need need any toolchains.)

1. Download small sample project: https://github.com/nikita-island/cargo-update-flickering
2. Run cargo update zip, observe windows-core updated in iana-time-zone and wmi, the last is unrelated to zip. Now cargo check is broken.
3. Run cargo update zip again, observe windows-core reverted to the old version. Now cargo check works again.
4. Subsequent invocations flip the state again and again.

Possible Solution(s)

No response

Notes

I tries to pin the dependencies as strictly as possible so that the reproduction keeps working even if the crates themselves will be updated.
But if the reproduction stop working for some reason, I have a shell transcript in the readme of the reproduction repo.

(Also tried in nightly)

Version

cargo 1.94.1 (29ea6fb6a 2026-03-24)
release: 1.94.1
commit-hash: 29ea6fb6a5db279426f4cc4e17aa385f05a0cfbc
commit-date: 2026-03-24
host: x86_64-unknown-linux-gnu
libgit2: 1.9.2 (sys:0.20.3 vendored)
libcurl: 8.15.0-DEV (sys:0.4.83+curl-8.15.0 vendored ssl:OpenSSL/3.5.4)
ssl: OpenSSL 3.5.4 30 Sep 2025
os: Fedora 43.0.0 [64-bit]

Download the linked cargo-update-flickering reproduction and follow the listed cargo update zip and cargo check steps, comparing the lockfile after repeated updates. Start by tracing the cargo update behavior for the requested package and its dependency resolution. Done means repeated updates are stable, unrelated packages are not changed, and the reproduction continues to pass cargo check.