Google contact groups would be very helpful. If you click on an email and want to add the contacts to a group, you would be able to see a dropdown of groups and you can click a check box next to each one. After you click them, they appear like tags.
Universal Contact Manager does a really good job at graphically displaying groups as tags (or labels), where they even allow you to color code the specific tags.
If you would like to further discuss please let me know and I would be willing to share design documents.
Thanks,