It's worth noting that it isn't just light pollution that can degrade the quality of a night sky, but also the so called seeing conditions. Even miles away from sodium street lights a humid or dusty night (even one that appears cloud free) will not produce great stargazing. I've seen the Milky Way from just outside the city of Durham on a cold, crisp winter's night, and yet struggled to see more than just a few of the brightest stars whilst camped beside the upper River Feshie, all because of how transparent the sky was.
To get the best opportunities to see things like the Milky Way and the Andromeda Galaxy you need to factor in the atmosphere and weather conditions alongside finding a good spot away from street lights. In general a cold, crisp winter's night will be better than a damp, mild autumn night. Usually the "best" skies are in the wake of a weather front - the air is generally much clearer and calmer and you'll get some stunning views.
I've had 13 nights out with the tent this year and I would say about two have produced truly "wow" skies so the best advice is just to keep on trying. Any wild camping location will give you a good opportunity, as long as the sky conditions co-operate