I have no idea if this is a conspiracy on the part of Microsoft but it sure is a productivity killer for me. In any case, here's what I've learned about how to get CTRL+M working with Lotus Notes:
First: This is the post that tipped me off that Bing Toolbar might be what's clobbering Notes:
Bing Ctrl+M doesn't work after installing new Bing toolbar
Next, I found this technote on how to uninstall Bing toolbar
Uninstall Bing Bar or Microsoft Silverlight
From there I followed these instructions:
To uninstall Bing Bar:
1. Click Start, and then click in the Start Search box.
2. Type appwiz.cpl, and then press ENTER.
3. In the Uninstall or change program list, click Bing Bar, and then click Uninstall.
4. Follow the on-screen instructions.
Here's what I got when I tried to uninstall Bing on a brand new PC:
Unfortunately for me, the uninstaller for Bing failed to successfully uninstall Bing but it did manage to remove enough of Bing that my CTRL+M is now working properly and I can be productive again.
I hope this helps.