What about... I'm not sure how the coding would work, but what about something like... The Librarian "research" one of your items. After a time period (or a fee, or both), he completes his research and will show you one (or more) items from the same set? I'm not sure there's a way for him to only display items not already in your inventory. If there isn't, the cost / number of items returned would have to be balanced with the chances of dud research - that is, if you have 13/15, the chances of 1 random item from the set being what you're looking for is low.
Did that make sense? If it can be done, it seems to balance the element of surprise with a collector's frustration.
Another thought would be for a fee he will tell you what item belongs to what number (like, Item #1 = triforce piece). That sort of breaks the fourth wall, though.