I could be way outta my league (in fact I think I am), but I think you're correct in the thinking you have to pay for some M$ crap. They give you the 'Verified Publisher' bit when you pay them to look at your app and give a thumbs up... If' I'm wrong... ah.. I tried..
