I got a chance to play around with address validation using Google geocode API v3. In my case I use the client side geocoding technique to submit full address (street address + suburb + state + postcode) to find out whether the results returned. The suburb, state and postcode is coming from a proper list.
What I found out with Google geocode is that when you submit full address, it also returns result with partial_match and they don't give an easy filter to exclude these results. Since I will always submit a full string address, I will just get the address when there is no partial_match property in the returned results. So far it works quite well for my situation.