Why cannot anonymous users vote, even though they have permission for it?
A possible explanation for this might be what is described in this issue on D.O: Fivestar Not Working for Anonymous Users with Cache Enabled.

A possible workaround for it is mentioned in Comment #9 of that issue, which states:


  ... When I set the author to anonymous on the field also set the field to allow users to vote on their own content, this appears to work as a crude work around.


Curious to hear if this somehow helps ...