I can reproduce this error message: when I tie a hash using AnyDBM_File, it selects NDBM_File, which implements Tie::Hash without a sub EXISTS { ... }, so exists on the tied hash does not work.

However, defined replaces exists in this case, because NDBM_File cannot store an undef in the database:

#!/usr/bin/perl
use Data::Dumper;
use Fcntl;
use AnyDBM_File;
die $! unless tie %h, 'AnyDBM_File', 'test.db', O_RDWR()|O_CREAT(), 06
+00;
undef $h{'b'}; # try to store an undef
print Dumper(\%h); # empty string is stored instead
print "still defined\n" if defined $h{'b'};
# we can confirm its existence:
#  if it's defined, it does exist
#  and no undefs exist there
delete $h{'b'}; # delete works as expected
print "does not exist\n" unless defined $h{'b'};
print Dumper(\%h);
__END__
$VAR1 = {
          'b' => ''
        };
still defined
does not exist
$VAR1 = {};
[download]

So using defined turns out to be the right decision.