I'd take a Tauren-like name and give it a 'death knight' twist.
Tauren last names appear to be a combination of a spiritual/earth word usually combined with 'hoof', 'pelt', 'horn', 'mane', etc. They also use 'totem' as part of their last name, likely Shamans.
So I would substitute the spiritual/earth word with an Unholy/Plague/Dead word.
Tradu's suggestion of "Blighthoof" is an excellent example of this. Having "Death Knight Blighthoof" would fit with "Arch Druid Runetotem" or "High Chieftain Bloodhoof" (A couple of the more famous Tauren NPCs in the game)
The fact that Runetotem and Bloodhoof are already established names for taurens makes it even easier. Death Knights use runes and have an entire spec dedicated to blood. You might want to stay away from Rune and Blood to distinguish yourself from a regular tauren.
Or not.
You can see a list of named NPCs in Thunderbluff
here to get an idea of how Bliz names their Taurens.
So anything like...
"Darkpelt"
"Deathhorn"
"Lichmane"
"Plaguetotem"
"Runehoof"
Should work?