Well, I'm not much of a golfer, but here is a proof of concept (at a whopping 258 strokes) that goes up to 999 nonillion... using spelling in Lingua::EN::Numbers (limiting to 0..99 is too boring)

# Update: 222 strokes by using a bareword and (for the fun of it) supp
+ort up to undecillion 10^36 (costs no extra chars due to bareword tri
+ck)
for f in 0 4 12 99 1024 1000024 999999999999999999999999999999999; do 
+echo $f | \
perl -E'@x=a33544355436688779880066555766=~/./g;$_=<>;chop;while(($a=$
+_)-4){split//,b999aabb87780;$x=4*!$_;$x+=hex(pop@_)*!!-$&+!!$1*($x[$1
+]+7)+$x[$2+20]+$x[$3]while s/(.??)([^1]?)(1?.)$//;say"$a is $x.";$_=$
+x}say"4 is magic."' ; \
echo; done

# Update: 224 strokes by including the suggested =~/./g shortcut and m
+oving output around a bit
perl -E'@x="033544355436688779880066555766"=~/./g;$_=<>;chop;while(($a
+=$_)-4){split//,"99aabb87780";$x=4*!$_;$x+=hex(pop@_)*!!-$&+!!$1*($x[
+$1]+7)+$x[$2+20]+$x[$3]while s/(.??)([^1]?)(1?.)$//;say"$a is $x.";$_
+=$x}say"4 is magic."'

# Update: 229 strokes by moving some conditionals into the regex
perl -E'@x=split//,"033544355436688779880066555766";$_=<>;chop;print;w
+hile($_-4){split//,"99aabb87780";$x=4*!$_;$x+=hex(pop@_)*!!-$&+!!$1*(
+$x[$1]+7)+$x[$2+20]+$x[$3]while s/(.??)([^1]?)(1?.)$//;say" is $x.";p
+rint$_=$x}say" is magic."'

# Update: Ah, ha! 239 strokes:  !!-$& will do it
perl -E'@x=split//,"0335443554366887798866555766";$_=<>;chop;print;whi
+le($_-4){split//,"99aabb87780";$x=4*!$_;$x+=hex(pop@_)*!!-$&+!!$1*($x
+[$1]+7)+($2>1?$x[$2+18]+$x[$3]:$x[$2.$3])while s/(.??)(.?)(.)$//;say"
+ is $x.";print$_=$x}say" is magic."'

# Update: 242 strokes, and works :), stealing some ideas from haarg & 
+thundergnat
perl -E'@x=split//,"0335443554366887798866555766";$_=<>;chop;print;whi
+le($_-4){split//,"99aabb87780";$x=4*!$_;$x+=hex(pop@_)*!!(0+$&)+!!$1*
+($x[$1]+7)+($2>1?$x[$2+18]+$x[$3]:$x[$2.$3])while s/(.??)(.?)(.)$//;s
+ay" is $x.";print$_=$x}say" is magic."'

# Update: Down to 258 strokes
perl -E'@x=split//,"0335443554366887798866555766";$_=<>;chop;print;whi
+le($_!=4){split//,"99aabb87780";$_?do{$x=0;while(s/(.??)(.?)(.)$//){$
+x+=hex(pop@_)*(0+$&?1:0)+($1?$x[$1]+7:0)+($2>1?$x[$2+18]+$x[$3]:$x[$2
+.$3])}}:($x=4);say" is $x.";print$_=$x}say" is magic."'

# 261 strokes:
perl -E'@x=split//,"0335443554366887798866555766";$_=<>;chop;print;whi
+le($_!=4){@m=split//,"99aabb87780";$_?do{$x=0;while(s/(.??)(.?)(.)$//
+){$x+=hex(pop@m)*(0+$&?1:0)+($1?$x[$1]+7:0)+($2>1?$x[$2+18]+$x[$3]:$x
+[$2.$3])}}:($x=4);say" is $x.";print$_=$x}say" is magic."'

999999999999999999999999999999999 is 321.
321 is 21.
21 is 9.
9 is 4.
4 is magic.
[download]