This was fun.
At least it passes all your test cases :)

#!/usr/bin/perl

use strict; # https://perlmonks.org/?node_id=11160313
use warnings;
use List::AllUtils qw( sample );
$SIG{__WARN__} = sub { die @_ };

for my $regex ( split /\n/, <<'END' )
\d{3}[-,.][A-V][a-z]{3}\d{2}
[a-c]{2}[-,.]\d{3}-[A-Z]{2}
abc*de?
a?b?c?d?e?
(ab?c){3}
END
  {
  print "\nThe Regex: $regex\n\n";
  my $strings = generate_random_strings( $regex, 10 );
  print "@$strings\n";
  }

sub generate_random_strings
  {
  my ($regex, $count) = @_;
  eval
    {
    my $tree = parse( $regex );
#   print $tree->show, "\n"; # NOTE uncomment to see parse tree
    return [ map $tree->run, 1 .. $count ];
    } or print " $@\n";
  }

sub CHAR::run { $_[0][0] }
sub ONEOF::run { sample 1, @{$_[0]} }
sub SEQ::run { join '', map $_->run, $_[0]->@* }
sub REPEAT::run
  {
  join '', map $_[0][2]->run, 1 .. sample 1, $_[0][0] .. $_[0][1];
  }

sub CHAR::show { "char @{$_[0]}\n" }
sub ONEOF::show { "oneof @{$_[0]}\n" }
sub SEQ::show { $_[0][0]->show . $_[0][1]->show }
sub REPEAT::show
  {
  my ($min, $max, $body) = $_[0]->@*;
  "repeat from $min to $max times\n" . $body->show =~ s/^/   /gmr
  }

sub node { bless [ @_[1..$#_] ], $_[0] }
sub error { die "ERROR: @_ \n" }
sub want { /\G$_[1]/gc ? shift : error pop }

sub parse
  {
  local $_ = shift;
  my $tree = expr();
  pos($_) == length or error "incomplete parse";
  return $tree;
  }

sub withranges
  {
  split //, shift =~ s/(.)-(.)/ join '', map chr, ord($1) .. ord($2) /
+gesr;
  }

sub expr
  {
  my $tree =
    /\G\\d/gc ? node ONEOF => 0 .. 9 :
    /\G\\w/gc ? node ONEOF => withranges '0-9A-Za-z_' :
    /\G\[(.+?)\]/gc ? node ONEOF => withranges $1 :
    /\G([- !"#\$%&',.\/:;<=>\@^_`~0-9A-Za-z])/gc ? node CHAR => "$1" :
    /\G\((?:\?:)?/gc ? want expr(), qr/\)/, 'missing right paren' :
    error 'operand expected';
  $tree =
    /\G\{(\d+)\}/gc ? node REPEAT => "$1", "$1", $tree :
    /\G\{(\d+),(\d)\}/gc ? node REPEAT => "$1", "$2", $tree :
    /\G\?/gc ? node REPEAT => 0, 1, $tree :
    /\G\*/gc ? node REPEAT => 0, 5, $tree :
    /\G\+/gc ? node REPEAT => 1, 5, $tree :
    /\G(?=[^)])/gc ? node SEQ => $tree, expr() :
    return $tree while 1;
  }
[download]

Outputs:

The Regex: \d{3}[-,.][A-V][a-z]{3}\d{2}

175-Mucn14 959-Qznv29 167.Rrfx39 554-Ibhv74 095.Pcwu22 659-Knno96 438.
+Qiou66 730.Cirx72 201.Rcmm97 823,Cade99

The Regex: [a-c]{2}[-,.]\d{3}-[A-Z]{2}

cc-249-NP ab-910-DK ab,430-GE bb-928-YG cb,283-BN ba.476-RJ cb-026-PC 
+cb-799-FW ba-301-TE bc-159-EP

The Regex: abc*de?

abcccde abccd abcccde abccccd abcccccd abccde abccccd abccd abd abcccc
+cd

The Regex: a?b?c?d?e?

d abde ad abc a bcde abd ce de be

The Regex: (ab?c){3}

abcabcac abcacabc abcabcac acacac acacabc abcacac acacac abcacabc abca
+cac abcabcac
[download]

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.