Not that I want to support Microsoft, but I had the same issue until I switched to HERE (Nokia's old product). Basically I have downloaded a map of my country (

Not that I want to support Microsoft, but I had the same issue until I switched to HERE (Nokia's old product). Basically I have downloaded a map of my country (~300 MB in size) and set the application to work offline. Works like a charm, does not feel like a downgrade at all.