This issue is about depends subsystem only.

Once everything is built, subsequent runs of make result in
make redoing some of the earlier done work.

There are 2 files which are being rebuilt.
config.site and .stamp_$(final_build_id).

config.site is rebuilt because

1. check-packages and check-sources are both phony and create no files.
2. A real file (config.site) depends on check-packages and check-sources.
   When a file depends on a phony prerequisite, the file is rebuilt every time. In
   this case, config.site is rebuilt every time.

.stamp_$(final_build_id) is rebuild because

1. every package (expat, boost, etc) is phony.
   .PHONY: $(1)
   See funcs.mk:239.
2. The rule for every package
   $(1): | $($(1)_cached_checksum)
   does not create any file.
   See funcs.mk:240.
3. A real file (.stamp_$(final_build_id)) depends on packages.
   When a file depends on a phony prerequisite, the file is rebuilt every time. In
   this case, .stamp_$(final_build_id) is rebuilt every time.

What can be done about this?

There are a few options.

Regarding config.site.

1. Given that subsequent runs of make do not download the tarball, then what is
   the purpose of computing the hash of the earlier downloaded tarball and
   comparing against the hash stored earlier in the stamp file?
   If some malicious person could substitute the local copy of the tarball, then
   that same person could store the new hash in the stamp file.

i see, that check-sources and check-packages were introduced in commit
235b3a7. The comment says this is for travis.
Given that travis is no longer used, we should figure out if this commit can
be reverted.

2. Another option is to mark check-packages and check-sources as not phony and
   introduce sentinel files.
   E.g.

check-packages: $(prereqs_of_check_packages)
    $(foreach package,$(all_packages),$(call check_or_remove_cached,$(package));)
    touch $@

check-sources: $(prereqs_of_check_sources)
    $(foreach package,$(all_packages),$(call check_or_remove_sources,$(package));)
    touch $@

In addition, both of these rules will need to have prerequisites.
In addition, the same trouble with .stamp_$(final_build_id) has to be fixed,
because config.site depends on .stamp_$(final_build_id).

3. Or keep the makefile as is. Apparently, this does not bother anybody.

As for .stamp_$(final_build_id), either the rule can be modified to create a
sentinel file and each package can be marked to be not phony or the keep the
makefile as is.

<!--- What behavior did you expect? -->
"Nothing to be done for 'all'." message from make.

<!--- How reliably can you reproduce the issue, what are the steps to do so? -->
Every time.

<!-- What version of Bitcoin Core are you using, where did you get it (website, self-compiled, etc)? -->
Latest soucrce from git.