andrei, I was just reading Programming Pearls this weekend, and Bentley was working on a very similar problem in chapter 12 (for generating random test examples, I think). Here's hoping I remember it correctly: (pseudo-code, of course)

int num_needed, num_available; /* pre-initialized */
List NewList;
for (element = List->first; 
      element->next != NULL;
      element = element->next) {
    if (@random@number@ < (num_needed/num_available)) {
        append(NewList, element); /* sort of - really just
the data */
        num_needed--;
    }
    num_available--;
}

"@random@number@" and "append" are mostly hand-waving, of course. This should guarantee that you'll get exactly num_needed elements in the new list, and the order from the original list is maintained (I wasn't sure whether that was important, from your posts). And I believe the distribution is uniform, too.

I hope this matches the problem you're working on.