PostcodeAnywhere is a really useful service for checking not only addresses, but email validation (dns lookup) and payment validation.
At this moment, there are integrations with lots of CMS and e-commerce apps. Why is not Wordpress is the list? :) Well, I suppose that integrate their service with Gravity Forms makes more sense.
Please, please, let me know if there is any possibility of doing this.