Current service discovery methods offer a single level of discovery reliability since they utilize a single method of discovery communication. However, the value of services vary by service type and consumer. Also, the number of similar services may vary. While it is acceptable to use best effort location in the case of a large number of similar or low-value services, it is undesirable to fail to locate available services in scenarios of high value services or situations where there is only a single instance of a desired service. Current schemes do not take into account variations in value or importance. This paper discusses the need for various levels of discovery reliability and our approach to fulfilling this need, including a discussion of development, testing, and experimental results. The results show that our reliability mechanisms provide higher levels of discovery probability when desired by a consumer.