Вот еще один подход:
SELECT u1.record_id, u1.first_name, u1.last_name, u2.record_id comp_record_id, u2.first_name comp_first_name, u2.last_name comp_last_name, u1.options FROM (
SELECT u.record_id, u.first_name, u.last_name, GROUP_CONCAT(pv.poll_id,'.', pv.option_id ORDER BY pv.poll_id, pv.option_id) options
FROM users u
INNER JOIN poll_votes pv ON pv.user_id = u.record_id
GROUP BY u.record_id
) u1
INNER JOIN (
SELECT u.record_id, u.first_name, u.last_name, GROUP_CONCAT(pv.poll_id,'.', pv.option_id ORDER BY pv.poll_id, pv.option_id) options
FROM users u
INNER JOIN poll_votes pv ON pv.user_id = u.record_id
GROUP BY u.record_id
) u2 ON u1.options = u2.options AND u1.record_id <> u2.record_id
WHERE u1.record_id = 1;
Два внутренних запроса идентичны и могут фактически быть превращены в представление. Внешний запрос просто объединяет два в списках вопросов / ответов, чтобы получить совпадения.