I'm revising this. The thread went into a direction I didn't want it to go into. I want to rally for quests to be added (similar to the stormwind start quest at level 8-9) in wherever. I'd prefer it to be undead to really show the meaning of it all. It's timeless. I want it to be parallel to the stormwind letter delivering one. It would mean a lot. I was REALLY hoping for it this Valentines Day, and I was really disappointed when I didn't see it. I really think it should be in Undead Lands though.
Here's how I see it:
You find an undead npc in a cage near Alliance (Gilneas Territory). The NPC is dead, but has a letter. He is gripping a letter and he wants you to deliver the letter to the alive human or undead spouse. It's a simple quest that would make a lot of us happy.