All problems are easily solved by having the Allied Race be resurrected at level 55 (or hell, start them at level 20) at the graveyard near each faction's Embassy by Mograine, have him monologue for a bit about the Ebon Blade, and at the end have him initiate the DK starting zone for you where you play as one of the named DKs in the current Acherus (which one depends on the spec you selected, such as "Marksopp the Tireless" as Unholy, "Ericus Deathbringer" as Frost, and "Minerva Ravensorrow" as Blood). If they wanted, they could even use the three DKs in the Argent Tournament in Icecrown ("Crok Scourgebane", the NPC who assists you in ICC, "Zor'be the Bloodletter", and "Illyrie Nightfall").
Mograine can say something like "To truly appreciate the depth of our duty to <faction name> and Azeroth as a whole, <player name>, you must first understand the adversity we have overcome in our service to this world. Let me know when you are ready, and I will show you the story of <one of the named Death Knights I mentioned>,".
It would allow them to keep the current DK starting zone but also keep it aligned with today's lore.
There's a loreful exception for Arthas being able to raise Nightborne and Highmountain Tauren, even assuming their seclusion was absolute. According to Alex Afrasiabi, the Creative Director of World of Warcraft, "Lich King subjugated valkyr and converted them to servants of the Scourge. As opposed to creating brand new ones." (source) As such, Arthas would most certainly have known about and been able to turn any of the denizens of the Broken Isles without ever setting foot there (since he can use the Val'kyr to resurrect them).
There are TONS of ways you can justify these new races being Death Knights, Blizzard likely just doesn't care enough to put in the effort.