Contacts many_to_many relationship with Users - how to use?

I think that you would want to use the Teams functionality to restrict access and Team-Based Permissions. 

This won't work for us since we don't want the rigidity of teams. This will be similar to, say, Google Docs, where you can add or remove users on an individual level for each doc.

I may just create an additional many-to-many relationship to handle this.

The link name is user_sync (see modules/Contacts/vardefs.php), so 'Contacts/:id/link/user_sync' would return a contact's users. Coming from users, the link name is contacts_sync (see modules/Users/vardefs.php).
But the contacts_users relationship is used for contact syncing with the MS Outlook Plug-in.

As Jeff said, Teams and Team-Based Permissions should do what you want. Remember that for every user in Sugar, a corresponding private team is automatically created. So you can add or remove access for individual users by adding/removing their private teams.

Wow thanks for this...I did not remember that because I didn't know until now...thanks so much!! Looking into the now. Does this apply for other modules as well (for instance, can a private team be used to restrict access to Notes)? I'll dig in myself but you may know more readily. 

Wow thanks for this...I did not remember that because I didn't know until now...thanks so much!! Looking into the now. Does this apply for other modules as well (for instance, can a private team be used to restrict access to Notes)? I'll dig in myself but you may know more readily. 

Absolutely. This applies to any module with Team Security enabled (including custom modules), and that's pretty much all ootb modules.