I don't know exactly if this is the type of solution you and BrowserUK were looking for (working towards), but it seems to work.. and should cut back on the rescanning thing. I left the (?{print pos($_)."\n"}) (it can be taken out if it is to much of an eyesore), to show where it starts matching, and uncommenting the use re 'debug'; line seems to confirm this. Anyhow here is the code:

use strict;
use warnings;
#use re 'debug';

$_ = "17341234173412341734123417341234";

my $i;
pos() = $i
   while s<\G
           (?{print pos($_) . "\n"})
           (.*?)(.)(...)\2
           (?{$i=pos()-4})
          >
          <defined $1?$1."A".$3."B":"A".$3."B">ex;
print;
__END__
0
1
3
4
9
11
12
17
19
20
25
27
28
A7AAB2BBA7AAB2BBA7AAB2BBA7AAB2BB
[download]

update: FWIW I did do much benchmarking using cmpthese in the benchmark module, and it appears that after all the hand waving, and tweaks, nothing seems to run faster than BrowserUK's substr solution, and probably the one I would go with for long strings of digits. But I would make one last change tweak first. That being changing the first . to a \d .
That is:

substr($a, $_, 5) =~ s[(\d)(...)\1][A$2B] for 0 .. length ($a);
[download]

Which should speed up the work the regex engine has to do as it will skip all the positions that do not start with a digit (and hence have already been turned into a letter (: ) For that matter the original could have been made better doing the same:
s!(\d)(...)\1!A$2B!;

-enlil