Autoconf generates makefiles and such which make assertions about the current state of the machine it ran on. Running a build using those those generated files out on a different machine (or the same machine in the future!) would seem to be defying reality. I think you have to accept that your build isn't deterministic unless you ensure your build has no dependencies except on tool binaries you check in right along with the code.
I believe you've misunderstood me (I can see how what I said was ambiguous), so let me clarify.
What I mean is that you're using a different version than is being tested by the other authors. So for example, if developer A used flex 2.35, but developer B has flex 2.36 installed on their system, they might get a different result (or a bug, or a security flaw in the resulting binary) etc.
I'll add that this isn't without cause - it has caused me personally many hours of errors.
Note that you can use autoconf to require exact versions, but then you require that the developer install an exact version of bison, even though they aren't touching the parser (or exact versions of autoconf even though they aren't touching the build system).
As I see it, you should either check in the flex and bison binaries themselves (and whatever runtime dependences they have) and only use those during the build, or accept that your build will fail and require maintenance as time goes by, doing whatever's simplest without trying hard to avoid that. Autoconf is intended to facilitate dependencies on components outside source control which happen to exist on a single machine, so it's only appropriate to use at all if you go the latter route.
Most people don't commit Makefile, but do commit configure and Makefile.in (both of which are still generated automatically, but it's not quite as bad as committing config.status or Makefile).
