I think app store is fair game, if the adds are well done they can actually be useful. Overcast adverts prove this.

I think they need to invest heavily in making it very very difficult (impossible?) for copy cat type apps to appear in search and making sure that adverts are clearly marked as adverts... It will just turn into a shit show otherwise...