Replying to myself - sorry.
OK for now the only solution for surveys I think is to turn on the Public setting after making any other changes to the permissions. The permissions page will always unset Contribute for The Public, and I think we need to keep this for safety (for the spam reason I mentioned a moment ago).
However, when you turn on Public for the survey, that will automatically grant Contribute access to it.
If it's already Public, you'll need to turn off Public, then save, then turn it on again and save again.
I'll try to think of a better long term solution, but this will work for now!
Thanks
Joe