<p>I'd like to generate unique random numbers between 0 and 1000 that never repeat (i.e. 6 doesn't show up twice), but that doesn't resort to something like an O(N) search of previous values to do it. Is this possible?</p>

You can do this:
Create a list, 0..1000.
Shuffle the list. (See
Fisher-Yates shuffle
for a good way to do this.)
Return numbers in order from the shuffled list.
So this doesn't require a search of old values each time, but it still requires O(N) for the initial shuffle. But as Nils pointed out in comments, this is amortised O(1).