There are many services. We perform our shipping through FedEx so we use their "Address Validation Service". The wrapper code to their API in python can be found here. The manual from FedEx can fe found here.
The are others like minfraud. You can pass fields such as shipping and billing address, phone numbers, emails, ip address, etc.. See more here. Based on the provided information, you will get a response that looks like this:
distance=0;countryMatch=Yes;countryCode=US;freeMail=No;anonymousProxy=No;binMatch=NA;binCountry=;err=;proxyScore=0.00;ip_region=CA;ip_city=Mountain View;ip_latitude=37.3860;ip_longitude=-122.0838;binName=;ip_isp=Google;ip_org=Google;binNameMatch=NA;binPhoneMatch=NA;binPhone=;custPhoneInBillingLoc=;highRiskCountry=No;queriesRemaining=4408;cityPostalMatch=;shipCityPostalMatch=;maxmindID=JBRH7OXI;ip_asnum=AS15169 Google Inc.;ip_userType=business;ip_countryConf=70;ip_regionConf=13;ip_cityConf=10;ip_postalCode=94040;ip_postalConf=;ip_accuracyRadius=999;ip_netSpeedCell=Corporate;ip_metroCode=807;ip_areaCode=650;ip_timeZone=America/Los_Angeles;ip_regionName=California;ip_domain=;ip_countryName=United States;ip_continentCode=NA;ip_corporateProxy=No;riskScore=34.0;prepaid=;minfraud_version=1.3;service_level=standard
MinFraud AVS check is more geared towards figuring out if a customer that is conducting business on your site is trustworthy.