Is there any way to search on a stream/feed for an item without authentication? /reader/api/0/search/items/ids returns Unauthorized error.
No, this is not possible. The primary use-case for search is to search over items the user has read in feeds they're subscribed to.