1. Install and enable Flag-6.x-2.x and Session API
2. In your recently_viewed flag configuration, allow anonymous users to both flag and unflag.
3. There's no step 3!

The thing is, it doesn't seem to be working 100% correct. Looks like a caching problem to me, will have look into it a bit closer. Anyway, give it a try and let me know what it's doing for you.