Makes sure the issue is repeatable and app devs are aware of the problem.
With a repeatable issue that also makes it easier to shortlist all the over address verfication/validation apps by installing them and making test orders to see which fail your businesses typical case of a bad address. https://apps.shopify.com/search?q=address%20validation%20verification
Fixing Addresses - Standard Operating Procedure
Consider first spending time & money automating the remediation process as much as possible to be as smooth and fast as possible.
Address verification is expensive and will always be error prone, so cheap apps and cheap solutions are why it does not work great.
I think around $15 per 1k validations is a very rough guideline as I don’t have an exact spreadsheet to back it up.
And I don’t know of any address validation/verification service that provides any type of actual guarantee, insurance, in sla.
So build into the model that some bad address always slip through either as mistakes or on purpose.
Which is why fixing the mistake should be as streamline as possible versus trying to do the impossible task of having perfect addresses for every order.
Custom apps with geo apis and low code services
If you are just USA based roll your own with USPS apis
https://www.usps.com/business/web-tools-apis/
If international , again roll your own but with something more broad
https://developers.google.com/maps/documentation/address-validation/overview#:~:text=The Address Validation API is a service that accepts an address, identifies the address components, and validates them. It also standardizes the address for mailing and finds the best known lat/long location for it
etc search “address validation service api”
Make sure to calculate billing api usage, hosting, maintenance, on top of the creation.
https://developers.google.com/maps/documentation/address-validation/usage-and-billing
“Appless” with lowcode services
Both the above example apis should support simple api-key auth so you could make it with a lowcode service such as integromat(now make), or zapier which have integrations with shopify.
Which skips having to setup a custom shopify app and host it.
Shopify automation apps
For scripting automation there’s also the usemechanic app for shopify.
Examples https://tasks.mechanic.dev/?tags=External%20API
https://tasks.mechanic.dev/?q=shipping%20address
https://tasks.mechanic.dev/standardize-uk-shipping-postcodes
convert to a “fix-shipping”-address process instead of email https://tasks.mechanic.dev/auto-verify-customer-email-addresses