Puede usar una combinación interna para filtrar las filas que tienen una fila coincidente en otra tabla:
SELECT DISTINCT records.id
FROM records
INNER JOIN data d1 on d1.id = records.firstname AND data.value = "john"
INNER JOIN data d2 on d2.id = records.lastname AND data.value = "smith"
Una de muchas otras alternativas es un in cláusula:
SELECT DISTINCT records.id
FROM records
WHERE records.firstname IN (
select id from data where value = 'john'
) AND records.lastname IN (
select id from data where value = 'smith'
)
