How to maintain consistency in a Many-to-many relationsship within embedded arrays!?

I'm going to describe a scenario which has taken alot of my time the latest month. 
My problem is about many-to-many relationsship, and how to make sure that the data are consistent.

Embedded in a client document there are two arrays: staffs and services. These arrays contains staff and service object, each staff containing zero or more references to services, and vice versa.
I have namned the references: "_id", and it will be an objectId, but in the example below it's simplified to numbers. 
The structure looks like this: 

A CLIENT DOCUMENT
{
  _id: ...
  staffs: [
    {
      _id: 1
      services: [6, 7] // references to services
    },
    {
      _id: 2
      services: [6]
    },
  ],
  services: [
    {
      _id: 6
      staffs: [1, 2] // references to staffs
    },
    {
      _id: 7
      staffs: [1]
    }
  ]
}

I want to be able to perform all CRUD operations on this structure an make sure that the data will be consistent.
At the moment i have found out three different wayt to handle this, and none of them feels perfect. 

Method nr 1. When saving a new staff, this is pushed to the staffs array, containing its array of references to services. In the same operation up to one reference can be inserted into services.$.staffs with the positional operator, but i cant insert all if them in the same operation. This forces me to insert the references in services in multiple steps, which makes the operation as whole non-atomic. If the program crash during the insert process I end up with a new staff which references to services doesn't match the services references to it. I have been experimenting with adding a status field to the staff-in-creation: "pendingCreation". When all reference insertions are complete we unset this, and if the app crashes during, we can pick up the operation because the "pendingCreatioin" field is not unset yet. But this leads to sligtly more complicated controllers and I have to build this restore-at-startup functions. 

Method nr 2. When creating a new staff, the controller query all services. The services referenecs are changed in memory and the new staff is saved to MongoDB along with the services array and its updated references. But what if another user also makes a new staff during the exact same time. The both request the services array, the both change it in memory, and one of them might get his changes overwritten. Then we also end up with a new staff which references to services doesn't match the services references to it. I have been experimenting with version stamping to avoid overwrites, and it seems to work. but this gives me new problem concerning the proper error messages when something goes wrong.

Method nr 3. All problems above feels like it all originates from the inability to create a new staff and all its proper service references in one atomic operation. But what if we change the data structure so that this becomes possible. If we remove all references from both staffs, and services, and instead create a third embedded array namned bindings, containing all connections between staffs and services. 

bindings: [
  {
    staff: 1,
    service: 6
  },
  {
    staff: 1,
    service: 7
  }, 
  {
    staff: 2,
    service: 6
  },
  // ...more objects
]

With this new structure it is indeed possible to create a staff, and in the same operation insert all its references.
The problem with this method is that is seem like a clumsy structure, with possibly a bit to much denormalized repeated data, and it also dont seems to be the advocated data structure for a many-to-many relationship in Mongodb.

Now I want your input! 
Which method do you prefer? How can this method be evolved to function even better?
Is there another way which i have not tought about?
How do i make sure that staffs/services are consistent at all time?