|MadSci Network: Astronomy|
You're right that the Moon is moving away from the Earth. Laser reflectors left by Apollo astronauts have allowed this recession to be calculated over the past thirty years. At the moment, the rate is approximately 3.8cm/year, and this is equal to the energy spent on raising tides on the Earth and Moon, and on the slowing down the Earth's rotation.
This recession rate is known to be irregular: it has been calculated that the rate was as low as 1.3cm/year before 650 million years ago. This variability reflects the position of the Earth's continents over geological time - a large supercontinent results in lesser tides and hence a lower recession rate. But, overall, the trend for a slowly receding Moon, and a spinning-down Earth is there.
So, will the Moon be lost from the Earth after a long period of time?
The answer appears to be "no".
Predictions suggest that the range will increase until the Earth and Moon become double synchronised, that is, both are tidally locked to one another. (So the Earth's day length would match the Moon's future orbital period of about 47 days, and the Earth-Moon distance would be about 550000km, compared to today's figure of 400000km). This won't occur for something like 50 billion years, by which point the Sun will be a white dwarf and will have passed through a red giant stage, which may result in the destruction of the Earth.
Assuming the Earth survives the conversion of the Sun to a white dwarf, then it appears likely that following the maximum range of the Moon-Earth distance, solar tides will start to tidally lock the Earth, leading to an Earth spin less than that of the lunar orbital period. In situations such as these, the Moon would then face orbital degradation, and, over time (and lots of it) it could eventually break up once inside the Earth's Roche limit, to become an enormous ring around the Earth.
On the recession of the Moon (and, particularly, how Creationists have it wrong) http://www.talkorigins .org/faqs/moonrec.html
Information on the long term effects of lunar recession from "Solar System Dynamics" by C.D. Murray and S. F. Dermott.
Try the links in the MadSci Library for more information on Astronomy.