What anonymity policy should MO have?
You say "As an internal moderation policy, we've always had less tolerance toward anonymous users but we never set any official rules or guidelines." This was repeatedly said, and in my understanding this is the policy. It is also in some old FAQs, IIRC. It seems it worked reasonably well.
In view of a comment let me add that I am not sure it makes sense to write down some suspension policy. Cases are individual and need to be handled on an individual basis. To fix some rules in abstract seems designed to lead to problems, and endless discussions. It seems reasonable to me not to be very restrained when facing users that seem to try to use the site in bad faith. Whether they do so under the auto-generated name, a pseudonym, their real-name; or a "real name."
The comment of Mad Scientist is in my opinion spot-on. Mainly, moderator action should be taken against behavior, not based on some secondary criteria. Indeed, doing the latter creates the separate issue that users try to work around it, and in doing so do things that might well be considered quite more problematic than anonymously asking a question on this site (even when in doing so they evade a ban).
Should we ban any users that use anonymizing tools to hide their identity?
Assuming you mean TOR and alike. Some users, not me, might have a need to use such technology that has nothing to do with trying to misbehave on MO. See for example this request of a real-name user. I do not think to just ban this on principle is a good idea.
It could be consider as a factor in moderation decisions though.
Should we require using real names?
Correct me if I am wrong but as far as I know and recall several (not to say most) of the bigger problems were actually caused by users under their real-name (or at least under what I took to be their real name, see below) or latter additional accounts that were, to those in the know, linkable to real-names. Thus, I do not quite understand what should be achieved by this.
Indeed, one might go as far as speculating that the real-names in the end had a negative effect. Users had to dig themselves in rather than to have the option to just walk away and perhaps come back in good.
Or, they pulled off stunts to get around the real-names encouragement policy.
On a practical note: there are masses of users in the network that might create an account with one click. Most of them will not be aware of such a policy. Would you intend to follow up on each such instance or delete on-sight? This will cause a lot of work and friction. Or, there would be a need for a technical solution.
Basically, I think one would have to change the sign-up drastically. However, then real names as display names would (still) not really be needed either. In fact it would be less needed then.
Should we maintain the status quo?
Yes, mainly. What annoys me personally are "fake real-names." Users should either use their real-name or something easily identifiable as not a real-name. If such "fake real names" would be discouraged or essentially banned it would have my support. (And I'd yet have to hear an argument in favor of them. There existence might also be encourage by the existing real names policy, one more point against it.) I know there might be some corner-case, where this might cause some issue, but by and large this should be reasonable to maintain. One might also make exceptions for common given names. But something that quite definitely looks designed to be read as a given-name name combo should be real or better avoided.
Are there other things MO could do to encourage civil and responsible behavior for all users?
You could moderate more tightly. I do not mean bans or moderator messages. Just delete comments that seem a bit rude or even just snarky (there is no need to make much ado about it, they will just be gone). On other SE sites moderation is a bit stricter. They have no real-names policy but are rather more civil (well some of them, some of the time, and I do not mean the one I moderate, which in any case is too small to be representative for anything).
Finally, I think one should resist the temptation to try to install policies one cannot enforce. It can back-fire. Some months ago (maybe longer) a user in a meta-post was quite explicit about this. They got banned permanently, and they try to evade the ban, and basically they have nothing to lose. While I do support that ban (even actively at times) and that user did things completely out of line, it still shows a problem with permanent bans.
Personally, I feel that at times moderation on this site is too emotional. At first, little is done since we are all a big community and one does not want to be seen as being oppressive or censoring. Then, things go too far, and many lose their patience and relatively massive actions are taken.
I believe sometimes it would be good issues would be escalated earlier but slower. The site has quite clear rules regarding content and conduct. They should be enforced on a daily basis, even if at times only by a stern comment.