After collecting 7 Keys of Terror from Bastion Keep, I decided to go after the Infernal Machine. Please confirm: Since you need 5NV to even stand a chance of getting the key from Odeg in the Fields of Misery, and you don't want to find him without the NV, that would mean I'd have to first do the Broken Blade quest (the one after the Khazra Den one) so I can accumulate all 5NV before I enter the Fields of Misery. At MP5 that should take me to Wortham before I encounter 5 champion packs. I guess I could do any quest in ACT1 as long as it's after Khazra, right?
PS: I've killed him 4 times with no key, but only one of those times did I have the NV required.
It doesn't matter what quest you're on. The only thing that is important is the NV5 stack.
I usually start in the Drowned Temple area - there are 2 small locations with elite pack and there's always 1-2 in the open. If you're lucky you'll also get this defend the hill event and voila... 5 stacks in 5-10min. If not lucky, than go to cemetery of the forsaken and enter 1-2 tombs and you're done. Easy.
i start with the crypts in the forsaken cemetery. easy 3NVs minimum from them and sometimes if lucky might get an elite in the cemetery itself. so that's 4. then move on to the fields and you will easily come across an elite before the keywarden. not sure if that is the perfect run but worked for me. got 2 keys from him in 3 attempts on MP2