BWA HA HA HA HA!
I finally figured out how to get the fatalities (and get drenched in blood).
First of all I have to thank bishounen for pointing out that you have to kill your opponent on the last round before the timer hits 40 seconds. I had no idea about that rule, and I don't think it was in Deuce's FAQ either.
OK, to get a fatality (No Contest) everytime:
-finish your opponent before the timer hits 40
-make sure that your opponent is not cornered. The fatalities won't work if your opponent has no room to stagger backwards
-finish your opponent with something sharp. Elbows, punches to the head, flying dogs, and blunt instruments don't get the job done
-be careful of the space between your sprite and your opponent's, and be careful of the amount of damage you do. If your opponent only has a sliver of life left, and you whack him from far away with Haohmaru's strong C, you'll just end up knocking your opponent off their feet, and you won't get the fatality. Get too close and your slash turns into an elbow, like Genjuro's close C, and that won't work either
-all three slashes, A, B, and C, have the potential to work as long as the spacing and damage is correct
to chop people in half, or have a fountain of blood shoot out:
-fulfill the above conditions, but do it after the timer hits 39 seconds. This will get you an old-style (Samurai 1 and 2) fatality
to get drenched from head to foot in your opponent's blood:
-kill your opponent after the timer hits 39 with a particular special move
-I've found two special moves so far: Haohmaru's ougi resshinzan (b, d, db + C), and Jubei's nikkakuratou (f, d, df + C). Again, spacing and damage seem to be relevant. I'm not sure if every character has a blood-drenching ending special or not, but I can confirm that these two characters do. I also had a blood-drenching happen to me with Charlotte, and Spoonman says he can do it with Bust Galford, so I'm guessing that there are more characters who can perform this.