Developing systems that perform discovery presents unique challenges, e.g., when compared to learning programs, since in general there is no teacher or example library available to train or evaluate a discovery system. In particular, the lack of gold-standard methods or examples makes the verification of discovered results and evaluation of system performance a very difficult problem. In this paper we address several issues of verifying a machine discovery system and discuss what one should and should not expect from the evaluation report of a discovery system. Recognizing that there is no direct way to verify the validity of a true discovery system, this paper proposes several indirect strategies one can adopt to assess the validity of discovered results. We then present our own set of novel link discovery tools as a case study to show how the proposed concepts can be applied to verify a real-world discovery system. In a time where computer science research has become extremely evaluation driven, researchers sometimes shy away from areas where results are difficult to evaluate. By discussing these issues with respect to discovery systems, we hope to provide a useful overview as well as – hopefully - a positive and encouraging signal to attract more researchers to work on machine discovery problems.