Here's how I've been farming the keys, up to you to decide if its the fastest way or not.
As for quest starting location, it doesn't matter as much. I usually start the game on the very last quest (except for the act 2 one since that puts you in the assault on Belial.)
General tips:
- You need 5 stacks of nv to make a key appear, it's not about magic find, just the 5 stacks.
- Do this on the highest MP you can tolerate and yet gain stacks/kill fast. By fast I mean, each run shouldn't take longer than 10 minutes tops. This is because there is a 10% chance improvement for each mp level, up to 100% at 10.
- Having multiple people helps. The act 1 and act 2 key wardens spawn in huge zones, so you can cover more ground with more people searching for them.
Key of Destruction
Odeg the Keywarden is in Fields of Misery in act 1. The fastest way to gain 5 stacks in act 1 is to hit up Festering Woods. Its can spawn up to multiple elites, 1-2 events, and has 2 dungeons with 1 guaranteed elite/champion in each. If you only have 3-4 stacks after this zone, just head straight to Fields of Misery as you'll probably run into 1-2 more packs before you find the key warden. Odeg always spawns with the molten effect, and he has a big fireball spell that can do ok damage. Other than that he's pretty easy. Keep in mind that he's a ranged attacker.
Key of Hate
Sokahr the Keywarden spawns in Dahlgur Oasis. The best place imo to farm up 5 stacks is actually the Dalghur Oasis itself. If you find the Keywarden before you have all 5 stacks, simply run away as he is incredibly slow and cannot catch you - come back when you've gathered the stacks from elsewhere in The Oasis. As for Sokahr himself, Dahlgur oasis is quite big and he can spawn anywhere in that zone, so having multiple people helps a lot. Sokahr has an electric attack and a whirlwind attack. When he starts whirlwinding, I recommend to back up since t hat attack hurts a lot. Other than that he's pretty easy.
Another note here is that he is a cake walk for a demon hunter using the ball lightning attack. Since he often (always?) appears with a slow missile shield these balls hang around sparking on him if you can stay far enough away that he isn't chasing you. Alternately make him chase you in a circle so the balls stay within his shield.
Key of Terror
Xah'Rith the Keywarden is in Stonefort. To gain stacks in act 3, I teleport to the keep 3 waypoint and work my way backwards through keep 3 and keep 2 until I have 5 stacks, and then I TP to stonefort. Having multiple people here won't help much since Stonefort is a very straight forward path rather than an open zone. Also make sure to check the offshoots on the side as he can sometimes spawn there. Xah'Rith is the hardest of the 3 key wardens as he teleports around a lot and have a high damage aoe attack. If you are a melee character, it helps a lot if you lure him to one of the many stair cases in the area so he can't run away as easily.
Infernal Machine Blacksmithing Plans
Dropped from Nekarat the Keywarden in Act 4. Luckily, you only have to find this once as its hard to build up 5 stacks in act 4. Start with the gardens and work your way through to the spire, hopefully you'll have 5 stacks by then. I got it on my first try so I can't recommend anything special for this guy.