In May I stopped installation of Windows 7 updates because one simple update seemed to be taking a long time with no activity. After that, the May 2015 Malicious Software Removal Tool would not go away. It would install successfully every time, writing to C:\Windows\debug\mrt.log and setting HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\RemovalTools\MRT\Version to the proper GUID. Nevertheless it would reappear after the next check for updates.
There were various ideas online, and I tried everything except deleting C:\Windows\SoftwareDistribution. Nothing helped. Eventually I just created a DWORD at HKEY_LOCAL_MACHINE\SOFTWARE\Policies\Microsoft\MRT\DontOfferThroughWUAU, setting it to 1 to disable offering of the tool via Windows Update. You cannot simply hide the update, because then last month's tool is offered instead, and so on.
I just removed that setting, wondering if the June updates might fix it. They did. I don't know what happened. Maybe the June Malicious Software Removal Tool set something that Windows Update finally recognized. All I know is I spent way too much time on this little problem.
BTW There is some useful information in KB891716.