Contact Information present
You have their e-mail or phone number in your database ?
If so, send any information to that contact information and only display a generic "thank you, if you are registered with us you will receive a confirmation to your registered contact information" message on the website. This message is always the same no matter if the user is in the DB or not.
In fact, to thwart timing attacks you should display the message and exit, and do the lookup and sending of mail or SMS in a background batch process.
Rate limiting, etc. was already mentioned, definitely recommended.
No Contact Information
If I understood correctly, you also have users without any contact information. These guys are tricky. The problem is that name and DOB are not secret information in any way. For most people, it takes minutes to find them out, and any skilled attacker can probably find them within an hour for 99% of people.
You need at least some additional information that is more difficult to find out and can work as a shared secret. That is the reasoning behind the various "mothers maiden name" or "name of your first pet" so-called security questions.
If you don't have anything else, there is no secure way to check. In this case you need to make those users identify themselves in some trusted way, e.g. by going to a physical location and showing their passport, or showing their passport on a webcam or some such step, depending on the sensitivity of the data.
This is a fundamental issue that you cannot solve with technology or math, because there simply is not enough non-public information present.
So check if any of the other fields stored in that DB can be used as identifying information.