How can I prevent users submitting a completely anonymous survey more than once?

Option 3 and "completely anonymous" are only compatible if the person who creates the codes throws them away after sending and cannot read the user's mail database.

In other words: it's impossible. There's always someone to trust, so why not trust the administrator. Depositor access to the database should work normally.

Option 5 I'd like to add: two databases and an agent. The user fills in a form of the first database, when transmitted the id-portion will stay in that db and the survey data will be moved to a survey database by means of the agent. The survey data will have to be removed completely from the original document. I think this is a better way to separate person and data.

I forgot to mention that the user has to log in for Option 5, in order to identify himself.

So here's the rub. If you are honsest, they may still not trust you. But, if you make an effort to make them trust you, then you end up doing it in a way where you COULD, if you wanted, track responses back to the user (i.e., you are not honest).

So, it comes down to:
a) you must make them think it is reaosnably trustworthy, even if their trust is based on misconcpetion
b) you yourself must be scrupulously honestm since the only way to guarantee once-only submissions while allowing (a) is for you to correlate surveys to the user in some way, but then choose to ignore the correlation

Here's how to do this, if you wish. Have each survey include a "token," which can be a randomly generated number, a sequentially generated number, or a hash of the username (preferably hashed via @HashPassword to make it less traceable).

Create a document in script for each user. You only need three fields filled in: FORM, USER , and TOKEN.  You can guess what TOKEN is. You are NEVER going to let anyone view this in Notes, and you will NEVER display the USER field in any view or form.
Set the form to automatically open in edit mode.
Add a COMPUTED field to the form (not when composed, not for display).  Name it USER and have its value calculate to "" (null string).
Optional: Add another COMPUTED field to the form (not when composed, not for display).  Name it TOKEN and have its value calculate to "" (null string).
Create a view with a single hidden sorted column, which is the TOKEN value.
Create an agent that will send a memo to each user, with alink constructed as follows:

"http://" + serverName + "/" + dbName + "/" + viewname + "/" + TOKEN

Now, if a user tries to put in a URL without the token on the end, the user will get the view which actually displays nothing. If an invalid token is put in, you get an error form the server (entry not found in index). If a validd token is put in, it finds THE MATCHING DOCUMENT, so the user can';t submit two different documents, only updates to this document. In additiion, if you put in the "option" I described above, then as soon as the survey is saved, that token code becomes invalid, so the user can't even go back in to the same survey document again. Also, when the user saves the surveym the user name is wiped out, so even if someone gets to the database, the only thing they can tell is which users have unfilled-out surveys pending (and by process of elimination, the names of those who responded, though no regular way to see which submission is theirs, unless they are the only survey on record).

Note: Someone could theoretically guess the UNIDs of the doucments, and get hold of someone else's unfilled out survey that way. In older versions of Notes, the NOTEID coudl be used the same way. It may also be able to hack in a replication conflict, allowing the same document to be submitted twice, though you shoudl be able to normally weed out the conflict documents.

A user coudl also use $First as the token, and walways get to the first document.  Yoru way around that is to have the view include both unfilled out surveys AND another special "error" form. Have the sort bring the error form to the top of the view.  That way, $First points to an error document instead of a survey document.

Your ACL should allow Anonymous=Editor to make this work, but Default=No Access. Seems backward, but it does what you want.