For the variable names, what about trying something similar to B::Deobfuscate? Take the deparsed code and walk through, renaming each variable in turn consistently but abstractly. E.g. if the first variable encountered is "$foo", replace all "[$@%&*]foo" with "${1}var1" everywhere. In otherwords, wherever "foo" is used as a symbol to refer to a variable, replace it with something predictable. So even if the other piece of code uses "bar" instead of foo, as long as the symbol exists in the same semantic place in the deparsed code, it will get replaced similarly by "var1".

My mind boggles at the regex challenge of doing this sanely on Perl code, so the rest of the solution is left as an exercise for the reader.

The other thing that occurs is not bothering with B::Deparse but going straight back to B and comparing at the op tree directly. Simon Cozen's has some examples of walking the op tree in Advanced Perl Programming (2nd ed). E.g. (almost straight from the text):

use B;

my $subref = sub {
  # some subroutine
}

my $b = B::svref_2object( $subref );
my $op = $b->START;

do {
  print B::class($op) . " : " . $op->name . " (" . $op->desc . ")\n";
} while $op = $op->next and not $op->isa("B::NULL");
[download]

B:: is way over my head, but the notion of walking the two trees and comparing operations directly seems like it might make it easier than worrying about interpreting the deparsed version of the same thing. (Let perl parse Perl.)