IANAL, but if the app you're building will be free, then I believe you can use the Google Maps API for free. It's limited to 15,000 geocoding requests per day, but according to the docs, that's tied to IP, not API key. You can get an API key immediately — no approval required. (If your app will not be freely available then you will have to sign up for Google Maps Premier.)
GMaps now has a REST-based geocoding API over HTTP (it used to be you had to use their JavaScript API, which was a pain on iPhone). It can return in JSON, which is trivial to parse using TouchJSON if you need the extra data, or CSV, which will be even easier if all you need is lat/lon. So, you can just create an object that conforms to the MKAnnotation protocol that will fetch the JSON/CSV from the API using an NSURLConnection or ASIHTTPRequest, parse it, and return the Point
variable as the coordinate
property and build your MapView as required.