Or use Perl 6:

    @results = @input.pick(*).uniq.[^$numwanted];
[download]

or some such...

Now that I think of it, if the shuffler (.pick(*)) is sufficiently lazy, that gets around all the problems of the other solutions. It doesn't need to visit all the values, but it'll still visit all the values if you ask for more values than exist uniquely, so it's also guaranteed to terminate.