Ok sorry If I start to get redundant but I'm trying to step through this in my head.
1. If you start to type an address and it autocompletes, do those fail consistently for the same contacts or is it random?
2. Does it also happen on addresses that don't autocomplete?