A Custom Shipping Add-on wouldn't be able to do that, since it is executed from the initial cart page, and not the Checkout page. So only the postal code and country are provided to it.
You could use custom JavaScript on the Checkout page, but I am not sure how you would go about validating that an address is 'complete and correct'.