Well, that's the distance from here to Saturn, so I'm going to guess that it would have escaped from Earth long before then. At the very least, it would be captured into the orbit of Venus, if not thrown away into the sun or straight out of the solar system.

But the farther away it gets, the less Earth's gravity affects it, so it should speed up too, right? It's velocity perpendicular to the Earth doesn't change, but the attraction drawing it in to the Earth weakens, so it should spiral out and away faster and faster every year. Correct me if I'm wrong on that.

Sounds to me like the status of the moon in 500 million years is... questionable. I really love realism, but I might recommend to /u/Kanaric that you just develop the situation the way you'd like to without worrying too much about it. If I were a player, I would probably be more pumped about being 500 million years in the future than I'd be worried about exactly what the status of the moon is. If it really is super important, share! I'd like to know what you've got in mind!