The coalescence of a massive black hole (MBH) binary leads to the gravitational-wave recoil of the system and its ejection from the galaxy core. We have carried out N-body simulations of the motion of a M=3.7 M⊙ MBH remnant in the “Via Lactea I” Milky Way-sized halo. The hole receives a kick velocity of Vkick = 80, 120, 200, 300, and 400 km/s at redshift 1.5, and its orbit is followed for over 1 Gyr within a “live” host halo, subject only to gravity and dynamical friction against the dark matter background. We show that, owing to asphericities in the dark matter potential, the orbit of the MBH is highly non-radial, resulting in a significantly increased decay timescale compared to a spherical halo. The simulations are used to construct a semi-analytic model of the motion of the MBH in a time-varying triaxial Navarro-Frenk-White dark matter halo plus a spherical stellar bulge, where the dynamical friction force is calculated directly from the velocity dispersion tensor. Such a model should offer a realistic picture of the dynamics of kicked MBHs in situations where gas drag, friction by disk stars, and the flattening of the central cusp by the returning hole are all negligible effects. We find that, in a Milky Way-sized galaxy, a recoiling hole carrying a gaseous disk of initial mass ~2 MBH may shine as a quasar for a substantial fraction of its “wandering” phase. The long decay timescales of recoiling MBHs predicted by this study may thus be favorable to the detection of off-nuclear quasar activity.