What you want is to open the vote only to users who have been registered for at least a week/month/etc -- but this probably won't help you, because if you're bringing up IP checks, it sounds like you aren't authenticating your users at all.
If you are trying to eliminate fraud, and you aren't authenticating your users, you probably get to throw up your hands and walk away. If you can be satisfied with a minimal reduction in casual fraud, there are a few things you can do.
Voter IP checks are a relatively low cost mechanism to try to keep multiple-voting down if you have nothing else to go on, but as you've noticed it can invoke a cost in terms of legitimate users prevented from voting, and does nothing whatsoever to prevent vote-stacking by recruitment of non-users, each of whom will have a legitimately different IP address (i.e. "Hey Slashdot/Reddit/Pharyngula/IRC-Channel-X, everyone go vote for this option on this poll!"). Single-user padding can still be done with botnets or large proxy lists or accounts on multiple machines (i.e. any university lab not behind a NAT).
What you're looking for is some bit of information that will be unique to a user. If you don't have that currently, you can create it by sending single-use tokens out to users in what is basically a vote-by-invite. This is still problematic, of course, if your users haven't already given you permission to e-mail them, or you don't know who your users are.
If you can lure your users into registering on the website, then you can authenticate votes that way, but it's dangerous to start that at the same time as a vote, because once again you face the possibility of a recruitment effort.
You can ask questions along with your poll that any real users should be able to answer easily, but non-users would not, and filter results that way, but you may discover that your users know less than you think, and nothing prevents fake voters from being provided with a cheat-sheet containing all the answers.
What you seem to be looking for, is a way to restrict input only to an unknown number of completely unknown people, and prevent them from providing input more than once or changing their apparent identity. That's not going to happen.