The best way for getting more visibility for apps on the App Store would be to build a social networking aspect into it. The one thing that is sorely lacking in the App Store is the viral nature of facebook. When one of my friens uses an application on facebook, I get a notification saying so. That is how I find most facebook apps I use. Apple could do a similar thing with the App Store, whereby every iPhone user has a profile page or something and a newsfeed. The newsfeed is populated by information from the contacts on the user's iPhone. This way apps would get a lot more visibility.
Depends how well the ad was targeted and how well quotas were set and screened for. There's a few good ways to attract survey respondents through ads, and a whole lot of bad ways.
