You can spoof Mac addresses but based on the bing windows search failure they are guaranteed to have a unique identifier available. I doubt it's easy if possible to link to online activity on different applications though such as web browsers.
microsoft can for sure, they already give each computer a unique id depending on the hardware inside the pc right
but I doubt microsoft would need to.
guess most tracking is based on cookies though which don't really link a computer to a person.
but I guess someone like facebook, they probably link your phone, computer browsers and computer if you installed some software they own.
just how secure do you think peoples personal data is, there are sure companies out there collecting tons of data from different sources, collecting them all together and trying to combine everything right.
you could probably go even further and use machine learning to track things you wouldn't think of that could identify an individual.
theres sure ways to track people through how their mouse movement is, typing habits etc and build a model for it that can identify different users.
your locations probably being tracked if you enable it by installing some app that logs what wifi networks you connect to and where they are, even if you never enable gps on your phone