yes, they have. If u go to gametrailers.com and go to the letter M u should find MK:Deceiption vids.
Here's the fatality one:

http://www.gametrailers.com/gt_vault/t_mortalkombat_dc_fatality.html

Yeah, I would say at least 8 have been shown. You can download the MK: Deception presentation video in the news section- E3 2004. near the end there are a hand full of fataites show off.

I was just watching Filter on G4TV tonight, and there was a real quick clip of Mortal Kombat Deadly Alliance on a girl shooting nails at someone. Now it was too quick for me to see it but the watermark on the bottom said MORTAL KOMBAT DEADLY ALLIANCE. But the shot looked like Meleena doing her nail spit fatality. I am going to try to watch it again if I can.

Mileena doesn't have that fatality. She has a bite-off-your-head fatality and a rip-your-leg-off-and-knock-your-head-off-with-it fatality.

Dude I know but I am almost positive of what I saw. It might be her second fatality. What saw was the 3D Camera moving behind this girl spittinng what appeared to be nails at someone. But it was so quick that I wish I taped it.
It was just on about 10 or 11pm, on Filter--G4TV.