You can extract the book name by itself with a regex, and compare using the regexes as keys for the hash:

$a=~/^((\d+ )?\w+)/
$abook=$1;
$b=~/^((\d+ )?\w+)/;
$bbook=$1;

if ($sortdata{$abook} > $sortdata{$bbook}) {
  return 1
 } elsif ($sortdata{$bbook} > $sortdata{$abook}) {
  return -1
 } else {
  return 0
 }
}  # END SUB byBiblicalBookOrder
[download]

This doesn't affect the contents of $a or $b themselves, so you can then do the additional sorting based on regexes that pull out the trailing sets of numbers.

edit: if you just want the book names and not the numbers, the regex would be something like /^((\d+ )?(\w+))/ and you'd take the value of $3 to get the book name without the leading number.