Yes. If, as you say, criminal history was not a bar to employment, why ask the question at all if you are going to run a background check anyhow? You contradict yourself by stating that "criminal history was not an bar to employment" but also that "The nature of the roles in question [...] required us to care about the pasts of the candidates." so it's difficult to understand why you are so firm on this point. Anyhow, there are plenty of protected groups of people that a prospective employer can't legally discriminate against, yet the discrimination still happens.
The applicant has to take a calculated risk when deciding whether to answer the question about criminal history honestly. Maybe a better question on the application, rather than asking outright about criminal history and discarding an applicant when you catch them in a lie, is asking about relevant convictions that might have some implications about whether that person has a history of violations in your area of practice, or present a conflict to your customers.