Is there a map API that will let me cache map data on my mobile phone?

We are in the midst of developing a mobile phone application which is map intensive, however, the area where this application will be used has very sparse cellular signals, and where the signal is available, there may not be data availability. Therefore, we need the ability to pre-cache map data in the application for the user's area so that the other aspects of the application can interact with that data. The solution can involve licensing or fair use, though we would prefer to minimize the capital outlay as this will not be a blockbuster application (very targeted niche we are delivering to). As we understand it, Google's map API does not permit cacheing and requires an always on connection. Any ideas?