I spent way too long trying to find this NPC and the coords provided always only led me to the middle of the road. So for those that are having trouble finding this guy I will provide what I hope will be more detailed directions to get to him.

From the Bullwark in Tirisfal follow the road east through the Western Plaguelands. Follow the road all the way across the entire zone until you get to the bridge that crosses the Thandoril River. Cross the bridge into the Eastern Plaguelands. After you get into EP keep an eye on your minimap and you will see mountains on both sides of the road. Keep going until you get passed all the mountain area and then keep an eye out for the Undercroft. The Undercroft is a tomb-like structure about 30 yards off the road on your right hand side and it will have unfriendly troll mobs pacing around outside of it. Now position yourself in the road so that the Undercroft is directly 90 degrees to your right. Now turn directly 90 degrees to your left and head straight north from the road. As soon as you leave the road your screen should say ""Merris Stead"" or something like that. Go about another 100 yards straight north and look for a single house on the top of a hill off to your left. The house looks just like those you'd see in Brill or Tarren Mill. Nathanos is there with two large Blighthounds (friendly) beside him. After you have ""discovered"" this area it will fill in on your world map. To find him again, the house will be located on your map in an area that looks like a C-shaped ""scar"" just north of the road in the SW portion of Eastern Plaguelands. The house is located directly in the middle of the C-shaped scar.

As a side note, Nathanos actually offers 3 quests initially, but after you complete and turn them in he will offer a few more; one to kill a giant worm, one to kill a giant bat and one to kill an elite courier guarded by 5 elite mobs that travel the road north of Corrahn's Crossing.

Due to WotLK expanding the map, the new coords for this NPC are : 22,68
Since Metalwraith won`t edit his post, he`s missleading people and I decided to post this.

I will confirm he is in front of the abandoned farm in Marris Stead. However, when I first arrived there he was nowhere in sight. I spent about 30 minutes looking for him, gave up, and returned to the farm...and there he was. Not sure why he wasn't there before, but that might be something you guys should be aware of. If he's not there at first, maybe quest around for a bit and come back. Maybe somebody killed him, I dunno.