Is there way to do batch geocoding (get lat/lon by address and vice-versa)?
Google Geocoding API has serious limitations (2,500 requests per day) and we always get a limit error. Their business license costs $10,000 and it is too expensive for us.
Service should work with different languages and different countries.
Service should verify address and return lat/lng. The addresses could be a strings with different formats.
We are ready to pay for such service and RESTful API is preferable.
Answer
I worked at SmartyStreets and what you describe is their core domain.
You might be interested in LiveAddress which transforms addresses into lat/lon and can process thousands of requests per second. It's geo-distributed across 3 data centers and has a RESTful endpoint. You can do up to 100 addresses per request. There's also a list processing version if you have an Excel or CSV file or something like that.
The highest price tag is $10k, but it gives you unlimited lookups for a year.
Some sample code is at https://github.com/smartystreets/LiveAddressSamples.
Their license agreement has no such restrictions to limit your usage. Dbaseman is right: you're getting limit errors because it's a violation of the TOS (unless you get a business license from them, but even then the addresses are "best guess" -- not standardized and verified like with a CASS-Certified service. That's something to keep in mind).