The answer probably depends how critical it is for you to receive support and possible customization for this service.
Google can certainly do this. Look into their XML and Geocoding API’s. You should be able to craft an XML message asking Google to return Map coordinates for a given address. If the address is not found (invalid), you will receive an appropriate response. Here’s a useful page: http://code.google.com/apis/maps/documentation/services.html#XML_Requests
Note that Google’s aim in providing the Maps API is to plot addresses on actual maps. While you can certainly use the data for other purposes, you are at the mercy of Google should one of their maps not exactly correspond to your legal or commercial address validation needs. If you paid for one of the services you mentioned, you would likely be able to receive support should certain addresses not resolve the way you expect them to.
In other words, you get what you pay for 😉 . If you have the time, though, why not try implementing a Google-based solution then going from there? The API looks pretty slick, and it’s free, after all.