Advances in sign language recognition technology can enable users of American Sign Language (ASL) dictionaries to search for a sign whose meaning is unknown by submitting a video of themselves performing the sign they had encountered, based on their memory of how it appeared. However, the relationship between the performance of sign recognition technology and user satisfaction of such search interaction is unknown. In two Wizard-of-Oz experimental studies, we found that in addition to the position of the desired word in a list of results, the similarity of the other words in the results list also affected user satisfaction.