Interesting script. Some comments:

You don't have to open a file to stat() it; lines 116-122 could be done with the (faster):

 $inode1 = (stat($keys1[$i1]))[1];
 $inode2 = (stat($keys2[$i2]))[1];
[download]

Also, you might want to try the File::Compare module as well as File::Find to eliminate the calls to the external (Unix) cmp and find programs; this would go a long ways toward making this script portable.

Also, Algorithm::Diff might be useful for comparing the lists of files. See File::DiffTree here for an example of using it for that.

update: added link to DiffTree.