I think direct advertising for your products is a suckers game. You have to compete against everyone for ad spots, and there's always another company that has better margins who will outbid you.

I've had success with two strategies:

1) Maintaining a semi-popular Open Source project adjacent to my app. The website of the open source project mentions my paid app. It's free advertising that noone can outbid.

2) Word-of-mouth: My app is recommended by users to others. It's also free advertising, you just need to make a nice product...