One of the ways to define an audience membership is via Windows security group. One can say that an audience consists of all members of a security group. This is often very convenient, as security groups often already reflect the organization's structure. However, setting up audiences on our company's SharePoint server I found that this simply didn't work. I set up an audience to consist of members of a security group that had 7 members. I found that the audience had only 1 member. I tried it with other groups - the results were utterly inconsistent. With some groups it worked, with some a few members were missing, with some all members were missing, and no clear pattern was seen.
After a long investigation the pattern was revealed. A security group member wouldn't make it to the group-based audience if the group was his/her primary group. It is a bug in SharePoint server, described in this blog post by Craig Gemmill for SharePoint Server 2003. I am using SharePoint Server 2007 and the bug is still present.
Apparently, it has to do with the fact that the user's primary group is not listed in its memberOf Active Directory attribute. The primary group's members attribute does not include the members with Primary Group attribute either. There are valid reasons for this design, described in this Microsoft KB article, but SharePoint Server, apparently, doesn't take Primary Group into account.
Thus the only solution was to reset the Primary Group of all users to Domain Users.