I would probably go with an SQLite database to store your information. You can have the contacts listed in a table with unique ids, then a table of labels. Finally, create a table that links one or more labels with each contact. Then you can just keep adding more labels.
-- http://mail.python.org/mailman/listinfo/python-list
