hi, my mouse had the same problem too, so I was searching through the internet to find the answer when I saw ur post.
I tried one of ur methods- pressing the power button for a few seconds, And it surprisingly worked and link to my mac successfully. For real I don't know what happens, but here are the details of my process, hope this can help u.
1.I open the system preference and found Bluetooth
2.then I started to press the power button for a few seconds ( the mouse was on ), then I saw the light blink slower.
3.Then a name appeared on the BlueTooth page, I click on it and it links successfully. But the name is (Mouse 3600), no name of Microsoft so u may somehow miss it.
4.Try it and see if it works!