VHormazabal, you were right.
I think I know what's going on, after looking at other types of Polls' options (ie. "Democracy AJAX", which I had before but stopped using.)
The reason why it tells my visitors that they've already voted when in fact they have NOT - is because they may be on shared IP addresses, possibly in a corporate network environment, and since my polls log by IP, it may recognize that the person had already voted.
So do you guys think maybe I should log by cookies instead? Will that pose the same problem? I DO want to log SOMETHING to prevent one person voting a million times. As much as I'd love to make my polls super popular :P I really want to keep all the votes valid cuz then, what's the point, right? I can sit here and ramp up the votes myself. :P
Thanks for the input!