How is DRUPAL_CACHE_PER_USER handled for anonymous users?
Yes. If a user is not logged in then uid is 0. So all anon users share the same user id.

I guess you will have to do your own caching, e.g. based on the IP address.