The string posted doesn't meat the needs. Here's what I've got (84 chars):
sub checker
{
my ($str) = @_;
for ('00' .. '99')
{
my $n = 0;
$n++ while $str =~ /$_/g;
die "'$_' appears $n times\n" if $n != 1;
}
}
sub generate
{
0 1 2 3 4 5 6
+ 7 8
#012345678901234567890123456789012345678901234567890123456789012345678
+90123456789012345
for$x(0..9){for$y(0..9){/$x$y/(/^$y/and$_="$x$_")(/$x$/and$_.=$y)
+or$_.="$x$y"}}$_
}
print "Generating ...\n";
my $test = generate();
print "$test\n";
print "Checking ...\n";
checker($test);
print "Ok\n";

Generating ...
9900102030405060708091121314151617181922324252627282933435363738394454
+6474849556575859667686977879889
Checking ...
Ok
I know it can be improved ...
Update: 78 chars and counting ...
#0 1 2 3 4 5 6
+ 7 8
#012345678901234567890123456789012345678901234567890123456789012345678
+901234567890
for$x(0..9){for$y(0..9){/$x$y/(/^$y/?$_=$x.$_:(/$x$/?$_.=$y:($_.=$x
+.$y)))}}$_
Update: 72 chars and counting ...
#0 1 2 3 4 5 6
+ 7
#012345678901234567890123456789012345678901234567890123456789012345678
+9012345
for$x(0..9){for$y(0..9){/$x$y/($_=/^$y/?$x.$_:/$x$/?$_.$y:$_.$x.$y)
+}}$_
for$x(0..9){for$y(0..9){$_=/$x$y/?$_:/^$y/?$x.$_:/$x$/?$_.$y:$_.$x.$y
+}}$_
 We are the carpenters and bricklayers of the Information Age. The idea is a little like C++ templates, except not quite so brainmeltingly complicated.  TheDamian, Exegesis 6 Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.
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! —
Posts may use any of the Perl Monks Approved HTML tags:
 a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, 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, 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: 
 &   & 
 <   < 
 >   > 
 [   [ 
 ]   ] 
Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.

