We've seen that the universe can be threatened by something that exists outside of time and shows up at all points in history, yet the Doctor doesn't encounter it or see any evidence of its effects until a certain point in his own personal history. The example that immediately comes to mind (but there are obviously earlier examples) is the cracks in time. Tom Baker didn't see the cracks, and he and his companions were not affected by all of time imploding on itself in the series 5 finale. Neither are future doctors, presumably. This seems to indicate a linearity outside of the standard flow of time the Doctor travels through. Let's call it hypertime for the moment.
All the has happened or will happen, the entire state of the flow of time, exists as a moment in hypertime. Like things change over time, time changes over hypertime. Before the Time War, Gallifrey existed in Earth's past and in Earth's future. After the Time War, it existed in neither. "Before" and "after" in this case means before and after a point in hypertime. One hypermoment, Gallifrey existed, and evidence of that could be seen throughout history. The next, our time was rewritten so only the Doctor existed. This happens constantly in hypertime.
Time travellers move at will through our 4 dimensional time, but no matter how far back or how far forward they travel, their perceptions move forward linearly in hypertime just as assuredly as ours do in normal time.
Gallifrey exists outside of normal time, but moves forward linearly in hypertime, which is why "time travel" is impossible in regards to it and we only see linear progress. The "higher races" that remember Gallifrey have some perception of hypertime.
Hopefully, this post makes sense, rather than sounding like the "Time Cube" page. Just think of it as time itself having time.