Проверять информацию - это хорошее и необходимое качество кадровой службы. Чтобы не получить "кота в мешке", рекомендовал бы обратиться в собственную службу безопасности (СБ), они прекрасно знают, как, не нарушая законы, получить правдивую информацию о кандидате на трудоустройство. Крупные компании имеют в составе своих СБ подразделения по проверке кандидатов.
Если в компании нет такой службы - можно обратиться в наёмные. Всё зависит от важности поста, на который претендует кандидат. Если вакансия связана с работой с финансами - это просто необходимо.