you probably are already aware of this but just wanted to share some ideas which I would have tried.
- Download.com I would definitely try and get my software listed there and see if they have some sort of promotions I can purchase. New and noteworthy kinds of things can give you an instant boost.
- Other download sites There are plenty of other download sites for windows software which are not as popular as download.com - but you should try and get your software on as many of them as possible.
One of them which I end up using besides download.com regularly are softpedia.com
The biggest advantage of these sites are that they show up on search engines very well.
- Google Adwords I would definitely spend some money here and optimize for google search adwords as plenty of times, I myself end up clicking on ads while searching for software.
- Windows 8 Marketplace Windows 8 is going to have a marketplae and it will be a good idea if you can try and get your app into it. Win 8 is scheduled to launch Nov 2012 - so its not that far off and early mover advantage might be valuable.
- Magazine and blog reviews In India, magazines like Digit, Chip, etc carry DVDs with software. You can write to as many relevant magazines as possible and get them to review ypur software as well as include it in their DVDs. Same for popular bloggers in your product's area of interest.
I'm sorry if all these ideas sound generic. I had written some Windows tools many years ago and I had submitted it to download.com and tucows.com then which were very popular.