Isn't it best to rely on a cloud service for this kind of thing? Addresses are being created and being changed every day, a local database would quickly become outdated.
His was only ZIP Codes. USPS only publishes ZIP Code updates once monthly, if I recall right. Technically they are copyrighted by the USPS and you are supposed to obtain a reseller license to publish official ZIP Code data.
The rate of change is very low, maybe a dozen changes per month at most. It wouldn't be unreasonable, depending on the app, to keep it reasonably up to date.
You could also have the app phone home every few days asking for up-to-date data,
or diffs, and storing it locally (it shouldn't be that big). Then release a new version every now and then with roll-ups.
Yes, I've been using it with a web service as a backup, but having it embedded in an app makes for a super fast and responsive city/state lookup on devices with potentially flaky connections.