Unnecessary rebuilds when using --remote_download_outputs=all in Bazel 8.5+ (regression)

Description of the bug:

After switching to a recent Bazel version in one of my projects I notice that Bazel considers files to have changed and performs rebuilds, even though files have not changed. I can reproduce the issue when using Bazel 8.5.0 and later versions of Bazel (I have also tested with Bazel 9.0.2). I am not able to reproduce the issue when using Bazel 8.4.2. The problem happens when using disk or remote cache together with the '--remote_download_outputs=all' flag.

Which category does this issue belong to?

Core

What's the simplest, easiest way to reproduce this bug? Please provide a minimal example if possible.

Minimal reproduction example:

MODULE.bazel

module(
    name = "test",
)

bazel_dep(name = "rules_java", version = "9.6.1")
bazel_dep(name = "rules_jvm_external", version = "6.10")

maven = use_extension("@rules_jvm_external//:extensions.bzl", "maven")
maven.install(
    name = "test_maven",
    artifacts = [
        "com.google.guava:guava:31.1-jre",
    ],
)
use_repo(maven, "test_maven")

.bazelrc:

build --disk_cache=~/test_cache
build --remote_download_outputs=all

Test script (test.sh):

rm -rf ~/test_cache
bazel build -s @test_maven//:com_google_guava_guava
bazel clean
bazel build -s @test_maven//:com_google_guava_guava
bazel build -s @test_maven//:com_google_guava_guava --explain=explain.txt
if grep "One of the files has changed" explain.txt; then
    echo "Files changed!"
    exit 1
else
    echo "No files changed, everything ok"
    exit 0
fi

Notice that when running test.sh with Bazel 8.5.0 the following is printed:

Executing action 'Building external/rules_jvm_external+/private/tools/java/com/github/bazelbuild/rules_jvm_external/zip/libzip.jar (1 source file) [for tool]': One of the files has changed.
Executing action 'Compiling Java headers external/rules_jvm_external+/private/tools/java/com/github/bazelbuild/rules_jvm_external/zip/libzip-hjar.jar (1 source file) [for tool]': One of the files has changed.
Executing action 'Compiling Java headers external/rules_jvm_external+/private/tools/java/com/github/bazelbuild/rules_jvm_external/librules_jvm_external-hjar.jar (3 source files) [for tool]': One of the files has changed.
Executing action 'Building external/rules_jvm_external+/private/tools/java/com/github/bazelbuild/rules_jvm_external/librules_jvm_external.jar (3 source files) [for tool]': One of the files has changed.
Executing action 'Building external/rules_jvm_external+/private/tools/java/com/github/bazelbuild/rules_jvm_external/jar/AddJarManifestEntry.jar (1 source file) [for tool]': One of the files has changed.
Files changed!

When running the test.sh with Bazel 8.4.2 the following is printed:

No files changed, everything ok

I am not 100% sure that this is not a bug in rules_jvm_external, however I've seen the same issue happen for C++ files when using the gcc_toolchain rules.

Which operating system are you running Bazel on?

Fedora 42

What is the output of bazel info release?

No response

If bazel info release returns development version or (@non-git), tell us how you built Bazel.

No response

What's the output of git remote get-url origin; git rev-parse HEAD ?

If this is a regression, please try to identify the Bazel commit where the bug was introduced with bazelisk --bisect.

No response

Have you found anything relevant by searching the web?

No response

Any other information, logs, or outputs that you want to share?

No response