We'd like to allow guests to vote on polls but for some reason they don't get the option.

unregistered / not logged in user group has Can Vote on Polls set to Yes.
Channel permissions...