Dirk, why doesn't the poll also store usernames?
It is possible to store only that a user has already voted for a poll and not what he has voted.
So there should be 3 possibilities:
1. IP based
2. Cookie based
3. User based
At http://fsim-ev.de we changed the polls plugin to this bahavior. You can check this out from http://fsim-ev.de/hg/geeklog (our mercurial repository)