Have you considered doing more marketing? Seems like you are in a spot where it would make sense.
* We also network with companies to get their content in our app (maps and data), which leads to links from their sites. This is a constant activity and we see this as the primary way to create a defensible market position in the category. Not only do we get something to sell, but our partners go out and sell their customers too.
* We have a popular hiking website (that's what we first build before switching to mobile dev) and this provides us with good PageRank for some searches, since we link our app site.
* We also have started to make all sorts of nice PR contacts - this seems to come organically the more you hang around a niche (hiking and backpacking for us). We will probably get our first real write-ups this summer.
* We have tried some Facebook and Google ads but we don't have a good handle on how well they convert, so we pretty much stopped that... just using a free credit to advertise our Android app on Google now.
* Our most effective strategy is we offer the 50 free promo codes we get from Apple for each release on our website, to anyone who asks. This leads to a lot of blog posts and App reviews.
* We also heavily cultivate our beta group, which leads to solid software and word-of-mouth.