I feel like this is similar to the death penalty debate though, where in response to the concern about executing innocent people, you hear "we'll only use it when it's a clear cut case" but either it ends up being used more than that, or it'd be used so rarely that it's not worth carving out a special case for it. How many things are on the clear cut level of Holocaust denial? And who decides what's clear cut enough to be excluded from free speech?
'Denial' isn't clear cut at all. You could deny it by saying it didn't happen at all, or that it happened in a different location, or by different people, or that the number of dead doesn't match the stated total(s). Is it denial to disbelieve a specific person was killed, or was killed in a specific manner? Is it denial to disbelieve some of the particulars of someones story? Free speech means exactly that; you're free to speak or you aren't.