Sorta like how My Immortal or whatever's popular these days is a comedy?
Okashii exaggerates a bit, insomuch as retribution wouldn't be instantaneous. But it'd happen. And you'd have to write Yukari being uncharacteristically retarded to have her get beheaded.
Also, Youkai die. It's the faeries that are reborn.
Youkai do have some degree of super regeneration. They can survive and heal from being cut in five pieces according to Japanese mythology. They're made of tough stuff, but take down the head and it's game over for youkai. Fairies, celestials and immortals can't be killed in any way. Gods and vampires are borderline cases. Gods can only die when their faith runs out, and Flandre claims that she tried to kill herself in various ways without any success, so vampires might be nigh immortal too.
I guess to perma-kill vampires you need to kill them like the very first vampires (when they were actually badass and hard-to-kill as opposed to modern vampires), which involved having to stake them in the heart, cut of their head, put garlic in their mouth, cut their body to pieces, burn the body and head to ashes and then throw the ashes over holy grounds BEFORE the full moon shines on the ashes. Only THEN will they permanently die. And yes, the full moon will cause the vampire to completely revive without a scratch on him/her/it even if he/she/it is utterly obliterated. The ashes NEED to be thrown on holy grounds like a church to stop the regeneration.
And according Remilia's profile she is capable of splitting up in swarm of countless bats. No matter how many of those bats you kill, as long as there remains ONE bat Remilia can revive. I wouldn't be surprised when it is revealed Remilia has hundreds of those bats hidden in safe places across Gensokyo or even the world to ensure that she doesn't die.