General idea: Grab the unique IN CAPITALS words from a line. For each IN CAPS, choose a distinct random product. Replace each IN CAPS with its product.

My choose-random-set-with-no-dupes algorithm:

For p in products-to-replace:
    c = int rand(@total - @chosen)
    For i in the sorted set of already-chosen items:
        last if c < i
        c++
    Insert c into sorted set
    new{p} = total[c]
[download]

I'm not sure how this algorithm stacks up against the "keep picking randomly until I get one I haven't already picked" algorithm. I'm guessing if @random_items >> $number_to_choose, it's not going to make much difference.

Here's the final code. Note that I took your example of "set IN CAPITALS quite helpfully" to mean that products can contain spaces. (See FROSTED FLAKES example).

my @random = map $_ x (3 + int rand 5), 'A'..'Z';
my $product_re = qr/\b[A-Z]+(?:\s[A-Z]+)*\b/;

while (<DATA>) {
    my %newname = map { $_ => 1 } /($product_re)/g;
    my @chosen = ();
    for my $prod (keys %newname) {
        my $c = int rand @random - @chosen;
        for (@chosen) {
            last if $c < $_;
            $c++;
        }
        my $i = 0;
        $i++ while $i < @chosen and $chosen[$i] < $c;
        splice @chosen, $i, 0, $c;
        $newname{$prod} = $random[$c];
    }
    s/($product_re)/$newname{$1}/g;
    print;
}
__DATA__
The respondent uses the following products XXX, YYYYY, and ZZZZZZ arou
+nd the house and they are considering using QQQQQQ, too. They are par
+ticularly impressed with ZZZZZZ.
Joe Smith used EGGO WAFFLES, FROSTED FLAKES, and RICE KRISPIES around 
+the house and he is considering using POST SHREDDED WHEAT too. He is 
+particularly impressed with RICE KRISPIES.
Bob likes CATS, DOGS, and ZEBRAS, but particularly CATS.
[download]