Sometimes the 'City' that you have to input is not what you expect, it's more like the general area. For one of the addresses that you can't find, try using the destination input map to go to the rough area, then try selecting the road name. Not ideal I know, but I've found it often works.