I have implemented a small macro, that does the job (at least for me). With minor changes it can be used to invalidate other cache variables:
# SYNOPSIS
#
# AX_RESET_HEADERS_CACHE(headers ...)
#
# DESCRIPTION
#
# This macro invalidates the headers cache variables created by previous AC_CHECK_HEADER/AC_CHECK_HEADERS checks.
#
AC_DEFUN([AX_RESET_HEADERS_CACHE], [
    AS_FOR([AX_var], [ax_var], [$1], [
        dnl You can replace "ac_cv_header_" with any prefix from http://www.gnu.org/software/autoconf/manual/html_node/Cache-Variable-Index.html
        AS_VAR_PUSHDEF([ax_Var], [ac_cv_header_${ax_var}])
        AS_UNSET([ax_Var])
        AS_VAR_POPDEF([ax_Var])
    ])
]) # AX_RESET_HEADERS_CACHE
and usage (in this loop $1 = some library (e.g. "netpbm"), $2 = headers (e.g. "pbm.h ppm.h"), $3 = locations (e.g. "/usr/include /usr/local/include")):
for ac_test_location in $3 
do
    dnl Save the current state
    ax_probe_library_save_CPPFLAGS=${CPPFLAGS}
    CPPFLAGS="$CPPFLAGS -I${ac_test_location}"
    AC_MSG_CHECKING([$1 for $2 in ${ac_test_location}])
    AS_ECHO()
    _AS_ECHO_LOG([CPPFLAGS="${CPPFLAGS}"])
    AC_CHECK_HEADERS([$2], [ac_lib_$1=yes], [ac_lib_$1=no])
    dnl We have found the location, leave the loop:
    if test "${ac_lib_$1}" = "yes"
    then
        break;
    fi
    dnl Restore the state to original in case of unsuccessful attempt
    CPPFLAGS=${ax_probe_library_save_CPPFLAGS}
    AX_RESET_HEADERS_CACHE([$2])
done