Network reconnaissance of addresses and ports is prerequisite to a vast majority of cyber attacks. Meanwhile, the static address configuration of networks and hosts simplifies adversarial reconnaissance for target discovery. Although the randomization of host addresses has been suggested as a proactive disruption mechanism against such reconnaissance, the proposed approaches do not exploit the full potentials of address randomization in provision of unpredictability and attack adaptability. Moreover, these approaches do not provide thorough analysis on effectiveness and limitations of address randomization against relevant threat models, including stealthy scanning and worms. In this paper, we present an effective address randomization technique, called random host address mutation (RHM), that turns end-hosts into untraceable moving targets. This technique achieves maximum efficacy by allowing address randomization to be highly unpredictable and fast, and adaptive to adversarial behavior, while incurring low operational and reconfiguration overhead. Our approach achieves the following objectives: (1) it achieves high uncertainty in adversary scanning by modeling address mutation randomization as a multi-level satisfiability problem; (2) it adapts the mutation scheme by fast characterization of adversarial reconnaissance patterns; (3) it achieves high mutation rate by separating mutation from end-hosts and managing it via network appliances; and (4) it preserves network integrity, manageability and performance by bounding the size of routing tables, preserving end-to-end reachability, and efficient handling of reconfiguration updates. Our extensive analyses and simulation show that the RHM distorts adversarial reconnaissance, slows down (deters) the attack, and increases its detectability. Consequently, the RHM is effective in countering a significant number of sophisticated threat models, including reconnaissance, stealthy/evasive scanning methods, and targeted attacks. We also address limitations of our approach in terms of effectiveness and applicability.