how about just filter out the recent ids with grep before doing the rand(), e.g.

# ...
my @not_recent = grep !defined( $recent_ids{ $_ } ), @ids;
my $idno;
{ use integer; $idno = (1+$#not_recent) * rand(); 
}
# ...
[download]

or alternatively, sort the items by $somehash ||= -M item into the array and just shift off the first three before doing the rand().