I am sure this has been here before, so I apoligize if you have seen it.
Anyway, I think there should be 2 vote categories.
The first is, "Can you use this software or do you find it useful?"
This would be the vote everyone can do, they dont need to download or use it to vote.
The second would be, "If you have downloaded this software, would you recommend it or is it good enough for you?"
If it costs money, this could simply be left as an open vote instead of requiring that it has been downloaded.
The best thing is that if you leave the second vote as open, to implement this would be quite simple. The code for the vote would simply need to be duplicated, the position changed so it fits under the first vote, and the question changed. Even without knowing the exact details of the webcode, I would dare say that even an amatuer could pull this off.(yes I make it sound simple, but I do know that it isnt always; but still I make the point)
As for checking if the download has occured, I would use a simple IP log that where IPs expire after 24 hours. Someone downloads the program, the IP gets logged. Upon clicking the second vote button, the site would simply check if that particular connection's IP was used to download the file. Obviously there is more too it than as simple as I make it sound, but I know it can be done without much difficulty because plenty of other sites do it easily enough.