This is a proposition of a schema that can be used to accommodate all the data needed for the previously listed functions. It should under no circumstances be regarded as authoritative. It is an example that should serve it's purpose, but it is likely you have to adapt it to match your specific needs. It should be noted, however, that it doesn't fit together seamlessly. The Microsoft Addressbook does not seem to use some of the fields it is presenting.
Any information is welcome.
The netscape address book has a similar problem. When a record is copied from an LDap directory to a local address book, some of the fields are lost. As the nature of an company-wide addressbook should discourage users to copy addresses locally, this is not a big problem though. But netscape address book has another little oddity though. When searching for addresses however, the associated attribute is simple nickname .