According to the YahooMaps Terms Of Service, you are not permitted to store the data that you gather from using the API. (specifically viii) "YOU SHALL NOT:"
(vi) use the Yahoo! Maps APIs with location information that is less
than 6 hours old and derived from a GPS device or any other location
sensing device;
(vii) use the Yahoo! Maps APIs with location information derived from
a GPS device or any other location sensing device where such
information was not uploaded to your application or service directly
by the end user;
(viii) store or allow end users to store map imagery, map data or
geocoded location information from the Yahoo! Maps APIs for any future
use;
(ix) use the stand-alone geocoder for any use other than displaying
Yahoo! Maps or displaying points on Yahoo! Maps;
(x) publish or display, or allow other users to publish or display,
any geocoded location information using any Yahoo! Maps APIs;
This is consistent with what I have seen in the TOS from Google, Bing, MapQuest, and Yahoo. The reason for this is that they benefit directly from being able to present the results to the end user. If their logo and "maps by google" isn't displayed, they don't get any "street cred" or exposure. Thus, their incentive to provide the service is gone. They make it very easy for you to use the service (extremely easy) but they also place reasonable limits. As long as you are using their data to make them money (even if they're just getting exposure) you are within the terms of their TOS. If you try to sidestep those terms, you run the risk of being cut off at any time. Not a happy story if your service is based on their service.
I have never used FME workbench, it looks really powerful (and at the same time, more complex than is needed), but will still be subject to the TOS of the data providers. Compare the FME workflow to this simple HTTP request to the US Street Address API by SmartyStreets:
https://smartystreets.com/products/single-address?street=1600%20ampytheatr%20Pkway&street2=&city=Mountain%20Vew&state=ca&zipcode=&address-type=us-street-components
It takes the following address and standardizes it (including obvious spelling correction), verifies that it is deliverable, and then geocodes it and breaks the address down into the various components outputting it as a JSON stream. If you don't read JSON, you can plug the output into a JSON formatter for much more readable results. (Feel free to use your own data in the URL string as well, for testing purposes)
1600 Ampytheatr Pkway
Mountain Vew, CA
becomes
1600 Amphitheatre Pkwy
Mountain View, CA 94043-1351
There are a number of commercial APIs available that do address verification, SmartyStreets just happens to be the one that I park my car at each morning. (Cdyne, StrikeIron, QAS are a few others that offer a similar service.) These commercial services offer you use of their data that is not bound by an overly-restrictive TOS. You can basically use the resulting dataset for just about anything short of competing directly.
You are correct that the geocoding data doesn't change very frequently and is something that can certainly be cached locally, or within your database to minimize the number of requests to the server. Good thinking.
Best Answer
Edit:
That's not possible with google because you are not allowed by the license to store the geocoding results (http://code.google.com/apis/maps/documentation/geocoding/#Limits)(see comments)One alternative option is to use the CloudMade Geocoding based on OpenStreetMap data. It has a Python API that you can use to get the coordinates, than you can easily output a simple delimited text file to be imported into fusion tables.