I posted this already to the php-dev mailing list and the recode module maintainer, but it didn't get any attention. I hope that helps.

Here's the patch again:
(cd ext/recode)

--- config.m4~  Sun Mar 26 21:47:25 2000
+++ config.m4   Mon Jun  5 12:31:20 2000
@@ -56,6 +56,7 @@
                AC_MSG_RESULT(yes)
 
                AC_DEFINE(HAVE_LIBRECODE, 1, [Whether we have librecode 3.5 or h
igher])
+               AC_CHECK_HEADERS(stdbool.h)
                PHP_EXTENSION(recode)
        else
                AC_MSG_RESULT(no)
--- php_recode.h~       Sat Mar 11 23:05:41 2000
+++ php_recode.h        Mon Jun  5 12:34:27 2000
@@ -45,7 +45,11 @@
  */
 #define HAVE_BROKEN_RECODE
 
-#include <stdbool.h>
+#ifdef HAVE_STDBOOL_H
+# include <stdbool.h>
+#else
+       typedef enum {false = 0, true = 1} bool;
+#endif
 #include <sys/types.h>
 #include <stdio.h>
 #include <recode.h> 


And here's (once more) the quote from the recode info file:

   The `<recode.h>' header file uses the Boolean type setup by the
system header file `<stdbool.h>'.  But this header file is still fairly
new in C standards, and likely does not exist everywhere.  If you
system does not offer this system header file yet, the proper
compilation of the `<recode.h>' file could be guaranteed through the
replacement of the inclusion line by:

     typedef enum {false = 0, true = 1} bool;