My short answer:
OHKO Clause bans four moves, but considering the Pokemon who learn them and the Pokemon who can counter them, I believe only Sheer Cold might be worthy of a ban. (I stress might.) Even then, I only think it's truly dangerous in the hands of three Pokemon in Lapras, Walrein, and Suicune--or four if Kyogre is counted. I can't support a blanket OHKO ban offhand, but I do believe Sheer Cold is worth testing (and possibly banning) independently of the others.
Also, for what it's worth, I think Machamp is a great comparison point. It gets to deal same damage with a base 100 power STAB move and give itself 50% free turn chances at the same time, which means that it mixes the reliability of a power move with the beat-a-counter potential of an OHKO move--and has a higher chance of getting a free turn than the OHKO move has of connecting even if the confusion only lasts one turn. Nothing can switch in except a Ghost, Slowbro, or Slowking, but the idea of banning Machamp isn't even dreamed of.
Longer answer elaborating on the individual moves:
Fissure
This move is learned by several notable Pokemon like Hippowdon, Doryuuzu, Flygon, Snorlax, Mamoswine, Randorosu, and Dugtrio, among other lesser options. However, I don't think I need to go over them in great detail considering how many powerful Pokemon who have historically seen common usage act as counters: Gyarados, Zapdos, Skarmory, Bronzong, Gliscor, Dragonite, Togekiss, Gengar, Forretress, Donphan, Cresselia, the Rotom forms, and the returning Salamence. On top of this, B/W adds five strong new Pokemon who ignore Fissure in Sazandora, Shibirudon, and the legendary trio, and there's also the Balloon item if it proves to have staying power. Finally, although it can't switch in directly, Mischievous Heart allows Erufuun to always Substitute before an OHKO move.
Except for Lapras, Walrein, Wailord, Torkoal, and Bastiodon, all Fissure users are Pokemon who commonly use Ground moves, which means that the switch-ins will likely be immune to Fissure simply because they're prepared for Earthquake or Earth Power. That much holds true even for Groudon.
In brief: Many (possibly even most) competitive teams will carry one or two Pokemon who counter a Fissure user's entire moveset without even meaning to, which suggests it's not worth banning.
Guillotine and Horn Drill
These two moves are slightly harder to work around. Skarmory and Forretress don't care about any of the users. Dusclops and Dusknoir have no trouble except for Crawdaunt and Kirikizan. Donphan has problems with the Water-type Guillotine/Horn Drill users and potentially Rapidash, but it does stop a fair number of others. Burunkeru is good to go unless it's facing Crawdaunt or Kirkizan. Spiritomb has pretty good defenses and no weaknesses, so it doesn't care about anything except maybe Nidoking. Gengar, for as fragile as it is, can get in on select things such as a Gliscor without Night Slash or Stone Edge or a Doryuuzu who dropped Rock Slide to use Horn Drill and/or Fissure and doesn't have Shadow Claw either.
Despite the small list of genuine counters in the strict sense, most users of Guillotine or Horn Drill simply aren't very good. Pinsir, Kingler, Crawdaunt, Kirikizan, Aianto, Dewgong, Seaking, and Rapidash all have at least one issue out of low Speed, poor defenses, poor offense, poor type coverage, common weaknesses, and a 4x weakness, which leaves them being fairly lame for any purpose except OHKOs. Like with Machamp, the fact that almost nothing can safely switch in doesn't equate to being broken. Gliscor (and Gligar along with it) stands out since it's been commonly-used, but it's never beating most Sturdy users or bulky Ghosts--and potentially not even some fragile Ghosts. Rhydon and Rhyperior are two of the better Horn Drill users, which is saying something since they're weak against so many common attack types.
In brief: Aside from maybe Nidoking and Ononokusu, who don't have any terribly glaring flaws, I'm not seeing users of these moves as troublesome either. Most of the Pokemon with Guillotine and Horn Drill have issues switching in or are easily revenged, so they're unlikely to get more than one successful KO per game with any of their moves--if they even get that far. The idea that they could get a successful KO on a 30% chance is no big deal; Pursuit users, Dugtrio, Magneton, and Magnezone are often good for one successful KO on a 100% chance and that's no problem.
Sheer Cold
Like sleep and unlike other OHKO moves, Sheer Cold would have virtually no counters even if it was the only move a Pokemon knew. Lapras, Walrein, and Suicune might very well be the core of the OHKO argument; when people worry about great OHKO users, they're likely thinking of these Pokemon. Unlike other Sheer Cold users such as, say, Smeargle and Dewgong, they're bulky enough to switch in and they're bulky enough to stay in.
Sheer Cold is a big deal.
Usually the response to something that's overpowered has been banning a Pokemon, not its most notable moves. But I don't think the choice needs to be that either a move is banned no matter what Pokemon uses it (OHKO Clause, Evasion Clause) or that a Pokemon is banned no matter what its moves are. If Lapras, Walrein, Suicune, or another Sheer Cold user proved to be broken, I wouldn't want a ban on the entire Pokemon or a ban on Sheer Cold. Latias without Soul Dew was once allowed in OU while Latias with Soul Dew was treated differently, so there's no contradiction if it was decided to ban Sheer Cold Suicune but keep non-Sheer Cold Suicune (and also keep Sheer Cold Glalie, Baibanira, and Articuno).
All in all: no on implementing a sweeping OHKO Clause. Evaluate the moves independently and I believe only Sheer Cold has any shot at being too powerful. It has fewer counters than the other OHKO moves, it's backed by more suitable Pokemon, and it's backed by more supportive movepools. Even then, 30% accuracy will never be good and two of its three best users are quite slow.