Немного изменив запрос Tomalak, чтобы он использовал индексы, если они присутствуют. Хотя, если в каждом поле нет индекса, в любом случае произойдет полное сканирование таблицы.
SELECT
*,
(
IF(name="john doe", 1, 0) +
IF(phone = "8183321234", 1, 0) +
IF(email = "johndoe@yahoo.com", 1, 0) +
IF(address = "330 some lane", 1, 0)
) as matchCount
FROM my_table
WHERE
name = "john doe" OR
phone = "8183321234" OR
email = "johndoe@yahoo.com" OR
address = "330 some lane"
HAVING matchCount >= 3