diff --git a/depends/Makefile b/depends/Makefile
--- a/depends/Makefile
+++ b/depends/Makefile
@@ -2,7 +2,7 @@
 
 # Pattern rule to print variables, e.g. make print-build_arch
 print-%:
-	@echo $* = $($*)
+	@echo '$*' = '$($*)'
 
 # When invoking a sub-make, keep only the command line variable definitions
 # matching the pattern in the filter function.
@@ -110,26 +110,31 @@
 include builders/default.mk
 include packages/packages.mk
 
-build_id_string:=$(BUILD_ID_SALT)
-build_id_string+=$(shell $(build_CC) --version 2>/dev/null)
-build_id_string+=$(shell $(build_AR) --version 2>/dev/null)
-build_id_string+=$(shell $(build_CXX) --version 2>/dev/null)
-build_id_string+=$(shell $(build_RANLIB) --version 2>/dev/null)
-build_id_string+=$(shell $(build_STRIP) --version 2>/dev/null)
-
-$(host_arch)_$(host_os)_id_string:=$(HOST_ID_SALT)
-$(host_arch)_$(host_os)_id_string+=$(shell $(host_CC) --version 2>/dev/null)
-$(host_arch)_$(host_os)_id_string+=$(shell $(host_AR) --version 2>/dev/null)
-$(host_arch)_$(host_os)_id_string+=$(shell $(host_CXX) --version 2>/dev/null)
-$(host_arch)_$(host_os)_id_string+=$(shell $(host_RANLIB) --version 2>/dev/null)
-$(host_arch)_$(host_os)_id_string+=$(shell $(host_STRIP) --version 2>/dev/null)
-
-ifneq ($(strip $(FORCE_USE_SYSTEM_CLANG)),)
-# Make sure that cache is invalidated when switching between system and
-# depends-managed, pinned clang
-build_id_string+=system_clang
-$(host_arch)_$(host_os)_id_string+=system_clang
-endif
+# Previously, we directly invoked the well-known programs using $(shell ...)
+# to contruct build_id_string. However, that was problematic because:
+#
+# 1. When invoking a shell, GNU Make special-cases exit code 127 (command not
+#    found) by not capturing the output but instead passing it through. This is
+#    not done for any other exit code.
+#
+# 2. Characters like '#' (from these programs' output) would end up in make
+#    variables like build_id_string, which would be wrongly interpreted by make
+#    when these variables were used.
+#
+# Therefore, we should avoid having arbitrary strings in make variables where
+# possible. The gen_id script used here hashes the output to construct a
+# "make-safe" id.
+#
+# Also note that these lines need to be:
+#
+#     1. After including {hosts,builders}/*.mk, since they rely on the tool
+#        variables (e.g. build_CC, host_STRIP, etc.) to be set.
+#
+#     2. Before including packages/*.mk (excluding packages/packages.mk), since
+#        they rely on the build_id variables
+#
+build_id:=$(shell env CC='$(build_CC)' CXX='$(build_CXX)' AR='$(build_AR)' RANLIB='$(build_RANLIB)' STRIP='$(build_STRIP)' SHA256SUM='$(build_SHA256SUM)' DEBUG='$(DEBUG)' ./gen_id '$(BUILD_ID_SALT)' 'GUIX_ENVIRONMENT=$(realpath $(GUIX_ENVIRONMENT))')
+$(host_arch)_$(host_os)_id:=$(shell env CC='$(host_CC)' CXX='$(host_CXX)' AR='$(host_AR)' RANLIB='$(host_RANLIB)' STRIP='$(host_STRIP)' SHA256SUM='$(build_SHA256SUM)' DEBUG='$(DEBUG)' ./gen_id '$(HOST_ID_SALT)' 'GUIX_ENVIRONMENT=$(realpath $(GUIX_ENVIRONMENT))')
 
 qrencode_packages_$(NO_QR) = $(qrencode_packages)
 
diff --git a/depends/funcs.mk b/depends/funcs.mk
--- a/depends/funcs.mk
+++ b/depends/funcs.mk
@@ -49,7 +49,7 @@
 $(eval $(1)_dependencies += $($(1)_$(host_arch)_$(host_os)_dependencies) $($(1)_$(host_os)_dependencies))
 $(eval $(1)_all_dependencies:=$(call int_get_all_dependencies,$(1),$($($(1)_type)_native_toolchain) $($($(1)_type)_native_binutils) $($(1)_dependencies)))
 $(foreach dep,$($(1)_all_dependencies),$(eval $(1)_build_id_deps+=$(dep)-$($(dep)_version)-$($(dep)_recipe_hash)))
-$(eval $(1)_build_id_long:=$(1)-$($(1)_version)-$($(1)_recipe_hash)-$(release_type) $($(1)_build_id_deps) $($($(1)_type)_id_string))
+$(eval $(1)_build_id_long:=$(1)-$($(1)_version)-$($(1)_recipe_hash)-$(release_type) $($(1)_build_id_deps) $($($(1)_type)_id))
 $(eval $(1)_build_id:=$(shell echo -n "$($(1)_build_id_long)" | $(build_SHA256SUM) | cut -c-$(HASH_LENGTH)))
 final_build_id_long+=$($(package)_build_id_long)
 
diff --git a/depends/gen_id b/depends/gen_id
new file mode 100755
--- /dev/null
+++ b/depends/gen_id
@@ -0,0 +1,74 @@
+#!/usr/bin/env bash
+
+# Usage: env [ CC=... ] [ CXX=... ] [ AR=... ] [ RANLIB=... ] [ STRIP=... ] \
+#            [ DEBUG=... ] ./build-id [ID_SALT]...
+#
+# Prints to stdout a SHA256 hash representing the current toolset, used by
+# depends/Makefile as a build id for caching purposes (detecting when the
+# toolset has changed and the cache needs to be invalidated).
+#
+# If the DEBUG environment variable is non-empty and the system has `tee`
+# available in its $PATH, the pre-image to the SHA256 hash will be printed to
+# stderr. This is to help developers debug caching issues in depends.
+
+# This script explicitly does not `set -e` because id determination is mostly
+# opportunistic: it is fine that things fail, as long as they fail consistently.
+
+# Command variables (CC/CXX/AR) which can be blank are invoked with `bash -c`,
+# because the "command not found" error message printed by shells often include
+# the line number, like so:
+#
+#     ./depends/gen_id: line 43: --version: command not found
+#
+# By invoking with `bash -c`, we ensure that the line number is always 1
+
+(
+    # Redirect stderr to stdout
+    exec 2>&1
+
+    echo "BEGIN ALL"
+
+    # Include any ID salts supplied via command line
+    echo "BEGIN ID SALT"
+    echo "$@"
+    echo "END ID SALT"
+
+    # GCC only prints COLLECT_LTO_WRAPPER when invoked with just "-v", but we want
+    # the information from "-v -E -" as well, so just include both.
+    echo "BEGIN CC"
+    bash -c "${CC} -v"
+    bash -c "${CC} -v -E -xc -o /dev/null - < /dev/null"
+    bash -c "${CC} -v -E -xobjective-c -o /dev/null - < /dev/null"
+    echo "END CC"
+
+    echo "BEGIN CXX"
+    bash -c "${CXX} -v"
+    bash -c "${CXX} -v -E -xc++ -o /dev/null - < /dev/null"
+    bash -c "${CXX} -v -E -xobjective-c++ -o /dev/null - < /dev/null"
+    echo "END CXX"
+
+    echo "BEGIN AR"
+    bash -c "${AR} --version"
+    env | grep '^AR_'
+    echo "ZERO_AR_DATE=${ZERO_AR_DATE}"
+    echo "END AR"
+
+    echo "BEGIN RANLIB"
+    bash -c "${RANLIB} --version"
+    env | grep '^RANLIB_'
+    echo "END RANLIB"
+
+    echo "BEGIN STRIP"
+    bash -c "${STRIP} --version"
+    env | grep '^STRIP_'
+    echo "END STRIP"
+
+    echo "END ALL"
+) | if [ -n "$DEBUG" ] && command -v tee > /dev/null 2>&1; then
+        # When debugging and `tee` is available, output the preimage to stderr
+        # in addition to passing through stdin to stdout
+        tee >(cat 1>&2)
+    else
+        # Otherwise, passthrough stdin to stdout
+        cat
+    fi | ${SHA256SUM} - | cut -d' ' -f1