Hours passed without any track or trace of this beast anywhere. I had been keeping a constant look out between using eagle eye, whispering passerby people, flying the wastes and camping his known spawn location. Two am rolled around, after nine hours of camping and fatigue finally set in. I called it a night, and decided to continue the following morning.
So, this morning rolls around at 7am, my alarm singing. I was hesitant to get out of bed because of how cold it was, but something told me to do a quick check of Madexx's spawn locations. So, alas I logged in ... to a red sky and a thunderous roar.
Deathwing...
The dragon tore through the area and killed me (for a third time I may add). I had desperately tied to escape by flying up and behind him but was too slow... Slightly frustrated with my new repair bill, I flew back to my body and ressed. Surely nothing would have survived that... even if Madexx was around he was dead now. Well that's when NPC scan proved me wrong.
More alarms blaring, I turn and look and there he is... walking out from the fires that Deathwing set across the wasteland. In my panic I didn't get a good screen shot of him coming out of the fire, but got one during the tame.

So, Madexx is my new firewalker. I was hoping for the blue skin, but in the epic display of how this beast presented himself, I will be keeping the black and red skin with no regrets :3
PS: I had the mini map up so you can see where He was wandering ^^