Sébastien, while this gives expected results on the AIX box here, it still has one subtle problem:
AC_TRY_LINK may fail due to missing declaration in <sys/file.h> _or_ due to missing implementation in libc.
The subsequent AC_CHECK_LIB won't fail when the implementation is in libbsd but the declaration is missing - this is the case on not-so-recent AIX5.3 (and the reason python worked there before).

Another minor nit is configure's output when libbsd is needed:
> checking for flock... checking for flock in -lbsd... yes
> yes

Anyway - I've hacked up another variant (with recent autoconf manual at hand), which really should cover all known situations now (additionally using cache-checks):

AC_CACHE_CHECK([for flock declaration], [ac_cv_flock_decl],
  [AC_COMPILE_IFELSE(
    [AC_LANG_PROGRAM(
      [#include <sys/file.h>],
      [void* p = flock]
    )],
    [ac_cv_flock_decl=yes],
    [ac_cv_flock_decl=no]
  )
])
if test "x${ac_cv_flock_decl}" = xyes; then
  AC_CHECK_FUNCS(flock,,
    AC_CHECK_LIB(bsd,flock,
      [AC_DEFINE(HAVE_FLOCK)
       AC_DEFINE(FLOCK_NEEDS_LIBBSD, 1, Define if flock needs to be linked with bsd library.)
    ])
  )
fi

Thank you anyway!