Not sure when they did this but Netflix has finally listened to my advice (and surely countless other potential users) and offered a search to anyone, not just subscribers.
The next logical step is to offer rentals on demand without a subscription, just a flat rate depending on the video.