Weird one: the upgrade to SP1 on the first MIM Service server went OK (a few hiccups with a missing data type in SQL, but I was able to create those and the upgrade went fine).
However, the installation on the second MIM Service server failed with very little information of any use in the log file.
I decided to uninstall MIM and got an error that the web application at “http://mysite.mydomain.com” did not exist. Sure enough, that Alternate Access Mapping was missing in SharePoint Central Admin on the second MIM Service server’s SharePoint configuration. I stopped the uninstall, added the AAM and the SP1 Upgrade finished successfully.