Many intelligent people, I suspect, believe that the Holocaust probably didn’t occur. This is likely because:
1) It seems very unlikely that a group now as powerful as “the Jews” could so recently have allowed themselves to be murdered on such a large scale, and
2) Many of their associates doubt that the Holocaust occurred, and
3) They live in countries where history books and newspapers promote obvious falsehoods. Thus, they have either read that the Holocaust was a myth, or they have reason to doubt the validity of writings that claimed the Holocaust happened.
If I met a Holocaust denier living in, say, Syria I would argue that nearly every sane person in the U.S., a nation with a free press, believes that the Holocaust did occur. But this Syrian could counter that the EU is considering criminalizing Holocaust denial. Such criminalization signals that many people living in the EU, also an area with a free press, doubt that the Holocaust occurred. Furthermore criminalization perhaps shows (from the viewpoint of the Syrian) that believers in the Holocaust want to foreclose debate on the subject and thus indicates that they fear they might lose an honest debate.