Try something like:

c:\@Work\Perl\monks>perl -wMstrict -le
"use Data::Dump qw(dd);
 ;;
 my $seq = 'xABCxABCxxxWXYxWXZxxxABCxxWXYx';
 ;;
 my $subseq = qr{ ABC \w* (?: WXY | WXZ) }xms;
 ;;
 my @all = find_all($seq, $subseq);
 dd \@all;
 ;;
 ;;
 sub find_all {
   my ($seq, $regex) = @_;
   ;;
   local our @hits;
   use re 'eval';
   $seq =~ m{
     ($regex) (?{ push @hits, [ $^N, $-[1] ] }) (?!)
     }xmsg;
   ;;
   return @hits;
   }
"
[
  ["ABCxABCxxxWXYxWXZxxxABCxxWXY", 1],
  ["ABCxABCxxxWXYxWXZ", 1],
  ["ABCxABCxxxWXY", 1],
  ["ABCxxxWXYxWXZxxxABCxxWXY", 5],
  ["ABCxxxWXYxWXZ", 5],
  ["ABCxxxWXY", 5],
  ["ABCxxWXY", 21],
]
[download]

Update: Using your original sequence:

c:\@Work\Perl\monks>perl -wMstrict -le
"use Data::Dump qw(dd);
 ;;
 my $seq = 'AATGGTTTCTCCCATCTCTCCATCGGCATAAAAATACAGAATGATCTAA';
 ;;
 my $subseq = qr{ ATG \w* (?: TAG | TAA | TGA) }xms;
 ;;
 my @all = find_all($seq, $subseq);
 dd \@all;
 ;;
 ;;
 sub find_all {
   my ($seq, $regex) = @_;
   ;;
   local our @hits;
   use re 'eval';
   $seq =~ m{
     ($regex) (?{ push @hits, [ $^N, $-[1] ] }) (?!)
     }xmsg;
   ;;
   return @hits;
   }
"
[
  ["ATGGTTTCTCCCATCTCTCCATCGGCATAAAAATACAGAATGATCTAA", 1],
  ["ATGGTTTCTCCCATCTCTCCATCGGCATAAAAATACAGAATGA", 1],
  ["ATGGTTTCTCCCATCTCTCCATCGGCATAA", 1],
  ["ATGATCTAA", 40],
]
[download]

Update 2: Remembering that DNA sequences may sometimes be loooong, it may be advantageous to pass the sequence by reference. Note that both the function and the function invocation must change.

c:\@Work\Perl\monks>perl -wMstrict -le
"use Data::Dump qw(dd);
 ;;
 my $seq = 'AATGGTTTCTCCCATCTCTCCATCGGCATAAAAATACAGAATGATCTAA';
 ;;
 my $subseq = qr{ ATG \w* (?: TAG | TAA | TGA) }xms;
 ;;
 my @all = find_all(\$seq, $subseq);
 dd \@all;
 ;;
 ;;
 sub find_all {
   my ($sr_seq, $regex) = @_;
   ;;
   local our @hits;
   use re 'eval';
   $$sr_seq =~ m{
     ($regex) (?{ push @hits, [ $^N, $-[1] ] }) (?!)
     }xmsg;
   ;;
   return @hits;
   }
"
[
  ["ATGGTTTCTCCCATCTCTCCATCGGCATAAAAATACAGAATGATCTAA", 1],
  ["ATGGTTTCTCCCATCTCTCCATCGGCATAAAAATACAGAATGA", 1],
  ["ATGGTTTCTCCCATCTCTCCATCGGCATAA", 1],
  ["ATGATCTAA", 40],
]
[download]

When I got deep recursion, I tried changing my regex, but I see that I just made it match the entire string. Is the problem still with my regex or am I using recursion incorrectly?

I don't see any need for recursion at all. As far as I can see, everything you want to do can be done in a properly constituted regex. There may be speed considerations that make a different approach preferable, but they can only be addressed by careful specification and benchmarking.

Update: To directly address your question about recursion:

sub find_coding {
         my ( $seq ) = @_;
         while ( $seq =~ /($regex)/g ) {
                 my $match = $1;
                 my $sequence = find_coding($match);
                 my $allmatch = find_coding($sequence);
                 print "Coding region: $allmatch", "\n";
         }
 }
[download]

Note also that the
    my $sequence = find_coding($match);
statement and the following
    my $allmatch = find_coding($sequence);
statement (were it ever to be executed) are meaningless because the  find_coding() function doesn't return anything meaningful; as best I can see, it would return (if it ever did) the return value of the print statement at the end of the while-loop. (Update: Changed this paragraph to address both statements.)

Update:

...the  find_coding() function ... would return ... the return value of the print statement at the end of the while-loop.