I've seen address verification services have positive, and maybe a few negative impacts, on user experience.
It's a positive when it makes autocompletion easy and helps to standardize the address formatting. Users feel secure when they find that they can select the validated, standardized address that matches their input. It's nice to not have to worry about perfect punctuation (when should I put commas or periods?) or capitalization. It's also nice to save a lot of typing when you find the correct suggestion early. Furthermore, depending on system requirements (shipping?), ensuring a valid address can be more important than most other considerations.
On the negative side, it can be annoying to users if the address they want isn't valid or doesn't have results from the service. It's annoying because it can be confusing: having a list of suggestions that don't match what you want can cause the user to be confused about whether they can submit an address that hasn't been validated. (Generally, if you use validated suggestions, it is a good idea to allow the user to still enter whatever they want, regardless of the suggestions; but how do you inform them that they can? It's a problem, but I think it's ok to allow users to just keep typing input if the suggestion doesn't match and not say anything. They may feel insecure that their address isn't pulling up matches, but at least they can submit what they want to submit.)
Sometimes, websites allow the user to input an address, and when they click submit, they validate the input. They then tell the user that the address didn't validate (couldn't verify a match), or they allow the user to choose a matching address. This works for some needs, but personally, I don't think that's as good of a user experience. Generally, this kind of set up doesn't allow users to submit their input when they don't want to use the suggestions.
Full disclosure: I work for SmartyStreets, an address verification service.