Looks like jdporter covered the major points, except for the fact that your use of "join()" (with the embedded "map" and "rand") won't work, either.

Slow things down a bit, give yourself some space, and use a loop to generate the candidate password -- put it in a subroutine, maybe, to keep it clear:

...
my $pw;
do {
   $pw = make_new_pw();
} while ( grep { $pw eq $_ } @stored );
...

# update: moved the declaration of @chars into the subroutine,
# where it belongs:

sub make_new_pw
{
    my @chars = ( "A" .. "Z", "a" .. "z", 0 .. 9, qw( ! @ $ % ^ & *) )
+;
    my $newpw = "";
    for ( 1 .. 17 ) {
        $newpw .= $chars[ rand @chars ];
    }
    return $newpw;
}
[download]

One closing tip: I've seen people get really bolixed because they are sent a password like "lXIg1v0WO" -- given the chance to control which letters are available to go into a random password, I would tend to leave "I1l" and "0O" out of the set, because they are too easily confused and misread.