Orem City's GIS group has published a Geocoder Web service. It has one method: give it an address in Orem and you get back a geocode. Not something the average citizen will want to access, but I think it's cool that not only have they got it, but it's online, accessible, and published at XMethods. From the description:

This web service is mostly useful in a GIS application. Here at Orem, we have about five on-line interactive maps and three desktop applications that consume this web service. Since we update our own centerlines, the geocoder is updated whenever we make any edits to the data source. We never have to awkwardly recreate ESRI locators.

It would be interesting for someone to create a UDDI registry of eGovernment Web services.