Tracking users and combatting fraud would definitely be an issue (just as it is for google), and you might have to set up trusted rings of users or some sort of web of trust rather than just trusting any user. It'd be interesting to try - tracking would have to be by browser cookie and actions like returning to results or upvoting/downvoting on the results page and you'd have to be very strict about fraud prevention from the start.

Perhaps more interesting than a specific ranking algorithm though is the idea of injecting random results into the mix. Perhaps Google has tried all these things already, it wouldn't surprise me and I know they look at user reactions like returning to results/time on page etc, but it'd be nice to see some search engine which is not owned and controlled by a massive corporation like MS, Google or Apple though - is anyone doing something interesting with common crawl?