We've been helping partners promote their applications via sponsored cross-linking for a while now. I recently had an idea that has been converting very well. I encourage you to give it a try, whether it's with us or with somebody else.
It's simple: combine a positive review from your application's review wall, your 75x75 directory icon, and the facebook install button. The sample we've provided is for the neat My Music application by our friends at Qloud.
On the publisher side, you should redirect clicks through a 'reflector' so that you can track the clicks you're generating.
On the advertiser's side, you should provide a link to the publisher with a spot for the publisher to fill in the current user's UID. The target of the link should log the clicking user and then redirect the user to the application. Later on, you can reconcile the referred users with your installed userbase to ascertain a conversion rate (and thus an eCPI--effective cost per install).
