Fraud-resistant voting protocols

In attempting to implement a large-scale voting system, one major concern is cheating, which may be committed by either the voters or the votees (by which I mean those administering the vote). Here are some ideas about how to fight many types of voting fraud. There is certainly a significant body of existing research related to voting so please excuse (and enlighten) me concerning any obviously-pertinent omissions.

Voting, version 0
Everyone registers ahead of time (to prevent illegal folks from participating). At the time of the vote, each voter must arrive at a local designated voting station where their registration is confirmed and they submit the information they wish to have counted on their behalf. Everyone trusts the administration to fairly count all votes accurately, and shortly thereafter the winners are announced.

This is meant to model the present voting scenario in the US. Here are the problems with this model:
1) Any errors or corruption within the administration are virtually transparent to the voting population. Logically, we only know if something has gone wrong when we vote for someone and the tally indicates they got zero votes. This very case occurred recently (which inspired me to start thinking about these challenges).
2) A voter may complain that their vote was mis-counted but we have no way of confirming or denying the voter's claim.

The following version is a very easy fix for some of these issues, but not all:

Voting, version 1
At the time of voting, each voter is given a secret unique id number which only the administration and the voter know. Once the voting is complete, two separate lists are published in a publicly accessible manner:

• Each unique id along with all the information of that person's vote
• Enough information (such as their name and zip code, e.g.) to uniquely identify each person who voted

The lists are completely separate so that each person's vote is only listed with thier secret id number, and not their name. Before you object to the immediate privacy concerns of publishing all voters' names, let's examine the benefits of this relatively easy-to-implement version. First, all voters can confirm that their vote was tallied correctly. If I voted for Jack Johnson, I can look up my id number to see that my vote was posted as I gave it. At the same time, no one else knows my number, so that my preferences are kept anonymous. Secondly, if we trust that most people are responsible enough to verify the veracity of their votes in the tally, then we can feel confident that the total scores are in fact correctly computed, since we can add up the votes for each candidate ourselves using the public posting. However, there is still the problem that the administration may have cheated by creating fictional voters in order to sway the majority one way or another. This is deterred by the list of names. The idea is that responsible voters pick a small random subset of these names, and confirm that these people actually exist. Unless the vote is very close, there will need to be a large percentage of fictional voters in order to cheat this way -- in that case, it is very likely that someone will notice some of the supposed voters do not exist.

But there are still problems with this system. Of course, some people are likely to object to having their names published - I'm not sure how to fix that (any ideas?) In addition, suppose a voter claims that his vote was not counted correctly. The voter knows the truth, but the administration still has no means to confirm the voter's claim. Although this system gives the voters close to complete knowledge of the fidelity of the tally, it does not afford a recourse in the case of an invalid count.

Hence, let us now consider

Voting, version 2
This case is an augmentation to version 1. Now we assume that all parties - voters and the administration - each have a means of digitally signing all transactions. (This unfortunately assumes that all voters have some access to a computer they can trust in order to generate a public/private key pair.) In order to vote, a person must submit a digitally signed form including their vote. Once the vote is received, they will immediately obtain a receipt, signed by the administration and confirming the information of that voter's choices.

This solves the problem of how to respond to a claim of an incorrect vote tally. If a voter claims a mistake has been made, they may back up their claim with the signed receipt they received. If a voter claims that their vote was mistakenly not counted at all, the administration can provide the signed vote they submitted. In either case the evidence or lack thereof is a strong indication in favor of one party or the other.

However, in the end, there remains the issue of voter privacy and verifiability. If we do publish, say, the names and addresses of all voters, who in reality would confirm their existences? Moreover, who would want to have strangers knocking on their door simply to check that they're not a fake voter? In the end it seems the fundamental problem of confirming that a person is real is the core challenge remaining here -- especially while protecting as much privacy as we reasonably can. Ideas?