It's not just London. Last week I tried to plan a route on my iphone from Beaconsfield (which is M40 J1) to Girvan in South Ayrshire and couldn't one, however it would plan a route to Glasgow which is a fair bit further north but reasonably simple; M40, M25, M1, M6, M74. If you are going to Girvan you have to come off the M74 and go down a few wiggly bits
I then tried on Live map and found the nearest I could get was a route from Uxbridge to Girvan. I ended up scrapping the idea and went by plane instead (I did remember to turn Waze turned off) but Waze worked a treat getting from the airport. No hanging around waiting for it to work out that it was 300 miles away from where it was last used unlike my old TomTom which could take up to 10 minutes.
I've just tried planning the route again in Live map and kept moving my start point further north until it worked, ended up getting one from Dumfries to Girvan which is not actually very far (65 miles) and it offered me three alternatives. All the following failed, Uxbridge, Watford, Northampton, Rugby and Carlisle. I tried each one several times and also tried each one to Glasgow which always worked.