Using service context AddLink, you can create N:N relationship in CRM. However you still need to check if the relationship has already been created between the two entities, otherwise you would get 'Insert duplicate key' error.
Thanks to this blog I don't have to create helper functions to check the existing relationship. Rather than using AddLink method that is tied to a service context, I just use the normal Associate method of the IOrganisationService:
Home » Dynamics CRM 2011 » CRM 2011 - Add many to many relationship + checking if relationship exists between entities (N:N)