If you still think that it is unbalanced when it only works on a natural 20 (IMO it is balanced) then you should consider removing the weapon or start, occasionally, giving NPCs the ability to negate the vorpal ability.
1. Disarm the fighter and take the sword away, start swinging the sword at the fighter and see how quickly he runs away.
2. Break the sword with sunder, not nice but effective.
3. Magically disenchant the sword or supress its abilities: antimagic field, targeted dispel magic, Mordenkainen's Disjunction.
3a. The Spellguant in MM2, with CR 12, can perform a disjunctive bite and render the weapon nonmagical.
4. Steal the sword, as discussed this can lead to many exciting chase scenes. You can also have the local artificer (Eberron Campaign class) remove the swords essense to gain craft points.
5. Start sending the PCs up against more oozes and undead or things that are immune to criticals. They cannot be beheaded if they are immune to criticals.
5a. Give important NPCs heavy fortification on their armour, it negates critical hits. Light fortification is a +1 armour bonus and grants a 25% chance to negate critical hits.
I quess that you do not have to punish the player for having a powerful weapon, just make their lives a little uncomfortable every now and again.