Thanks for the bug report and fix. I installed the attached patches. The first is Andreas's fix with somewhat-different commit message; the second contains more documentation about this.

I wish Perl supported precise file timestamps but we gotta work with what we have.

(file #51848, file #51849)

It's an upstream formward of downstream https://bugs.gentoo.org/782985 bug reported by Ionen Wolkens.

There `automake` run against outdated autoconf fails with version mismatch error. Here is full minimal reproducer:

$ cat Makefile.am
# empty

cat configure.ac
AC_INIT(bug, 0.0.0)
AM_INIT_AUTOMAKE([1.6])

AC_CONFIG_FILES([Makefile])
AC_OUTPUT

cat torture.bash
#!/bin/bash

die() {
        echo "FATAL: can't continue"
        exit 1
}

artificial_delay() {
        # https://bugs.gentoo.org/782985#c0
        [[ -n $ARTIFICIAL_DELAY ]] && sleep $ARTIFICIAL_DELAY
}

while :; do
        # remove all intermediate files from previous runs
        rm -fr -- aclocal.m4 autom4te.cache configure configure~ install-sh Makefile.in missing

        # generate aclocal and friends with older autoconf-2.69/automake-1.13
        aclocal-1.13 --force && autoconf-2.69 --force && automake-1.13 --add-missing --copy --force-missing --foreign || die

        # generate a trace (Gentoo does a bit of introspection for existing build system before a major update to new autoconf/automake)
        autoconf-2.71 --trace=AC_DOES_NOT_EXIST || die
        artificial_delay

        # a workaround
        #rm -rfv -- autom4te.cache

        # move to a new version of autoconf-2.71/automake-1.16
        aclocal-1.16 --force && /usr/bin/autoconf-2.71 --force && automake-1.16 --add-missing --copy --force-missing --foreign || die
done

The output:

bad:

+vebatim+
$ bash -x ./torture.bash
+ :
+ rm -fr -- aclocal.m4 autom4te.cache configure configure~ install-sh Makefile.in missing
+ aclocal-1.13 --force
+ autoconf-2.69 --force
aclocal.m4:17: warning: this file was generated for autoconf 2.71.
You have another version of autoconf.  It may work, but is not guaranteed to.
If you have problems, you may need to regenerate the build system entirely.
To do so, use the procedure documented by the package, typically 'autoreconf'.
+ automake-1.13 --add-missing --copy --force-missing --foreign
configure.ac:2: installing './install-sh'
configure.ac:2: installing './missing'
+ autoconf-2.71 --trace=AC_DOES_NOT_EXIST
+ artificial_delay
+ [[ -n '' ]]
+ aclocal-1.16 --force
+ /usr/bin/autoconf-2.71 --force
+ automake-1.16 --add-missing --copy --force-missing --foreign
configure.ac:2: error: version mismatch.  This is Automake 1.16.4,
configure.ac:2: but the definition used by this AM_INIT_AUTOMAKE
configure.ac:2: comes from Automake 1.13.4.  You should recreate
configure.ac:2: aclocal.m4 with aclocal and run automake again.
+ die
+ echo 'FATAL: can'\''t continue'
FATAL: can't continue
+ exit 1
-verbatim-

good:

+vebatim+
$ ARTIFICIAL_DELAY=1 bash -x ./torture.bash
+ :
+ rm -fr -- aclocal.m4 autom4te.cache configure configure~ install-sh Makefile.in missing
+ aclocal-1.13 --force
+ autoconf-2.69 --force
aclocal.m4:17: warning: this file was generated for autoconf 2.71.
You have another version of autoconf.  It may work, but is not guaranteed to.
If you have problems, you may need to regenerate the build system entirely.
To do so, use the procedure documented by the package, typically 'autoreconf'.
+ automake-1.13 --add-missing --copy --force-missing --foreign
configure.ac:2: installing './install-sh'
configure.ac:2: installing './missing'
+ autoconf-2.71 --trace=AC_DOES_NOT_EXIST
+ artificial_delay
+ [[ -n 1 ]]
+ sleep 1
+ aclocal-1.16 --force
+ /usr/bin/autoconf-2.71 --force
+ automake-1.16 --add-missing --copy --force-missing --foreign
+ :
+ rm -fr -- aclocal.m4 autom4te.cache configure configure~ install-sh Makefile.in missing
+ aclocal-1.13 --force
+ autoconf-2.69 --force
aclocal.m4:17: warning: this file was generated for autoconf 2.71.
You have another version of autoconf.  It may work, but is not guaranteed to.
If you have problems, you may need to regenerate the build system entirely.
To do so, use the procedure documented by the package, typically 'autoreconf'.
+ automake-1.13 --add-missing --copy --force-missing --foreign
configure.ac:2: installing './install-sh'
configure.ac:2: installing './missing'
+ autoconf-2.71 --trace=AC_DOES_NOT_EXIST
+ artificial_delay
+ [[ -n 1 ]]
+ sleep 1
+ aclocal-1.16 --force
+ /usr/bin/autoconf-2.71 --force
+ automake-1.16 --add-missing --copy --force-missing --foreign
+ :
+ rm -fr -- aclocal.m4 autom4te.cache configure configure~ install-sh Makefile.in missing
+ aclocal-1.13 --force
+ autoconf-2.69 --force
aclocal.m4:17: warning: this file was generated for autoconf 2.71.
You have another version of autoconf.  It may work, but is not guaranteed to.
If you have problems, you may need to regenerate the build system entirely.
To do so, use the procedure documented by the package, typically 'autoreconf'.
+ automake-1.13 --add-missing --copy --force-missing --foreign
configure.ac:2: installing './install-sh'
configure.ac:2: installing './missing'
+ autoconf-2.71 --trace=AC_DOES_NOT_EXIST
+ artificial_delay
+ [[ -n 1 ]]
+ sleep 1
...
-verbatim-

Explanation of `torture.bash`:

The script emulates Gentoo's behaviour of introspectinf existiong build system before safely regenerating `./configure` and all of it's depends to more recent `autoconf`/`automake`.

To do it the script runs `autoconf --trace=...` and then runs everything else.

Explanation of failure:

When `autoconf-${new} --trace=...` / `aclocal-${new}` / `automake ...` is executed within one second it tricks `autom4te` to consider traces up to date and does not regenerate traces (and breaks). `autom4te` has the following comment: https://git.savannah.gnu.org/cgit/autoconf.git/tree/bin/autom4te.in#n913

  # The youngest of the cache files must be older than the oldest of
  # the dependencies.
  # FIXME: These timestamps have only 1-second resolution.
  # Time::HiRes fixes this, but assumes Perl 5.8 or later.
  my $tmtime = mtime ($tfile);
  my $omtime = mtime ($ofile);
  my ($file, $mtime) = ($tmtime < $omtime
                        ? ($ofile, $omtime) : ($tfile, $tmtime));

`sleep 1` introduces enough delay to notice cache staleness between `autoconf-${new} --trace=...` / `aclocal-${new}`.

Thanks!