Could you provide a sample address that is failing to geocode? Sometimes, addresses are just something like “1 Privet Drive” (without city and country), instead of “1 Privet Drive, Hogarts, England”. Google Maps uses some guesses to fill in the city and country, whereas your app will need that.
Ben, if you had a lot of addresses, they take some time to geocode but they eventually do. And once they do, they are cached for subsequent use across all users.