I finally found time to update Medusa's desktop tool to GTK 2.4. The code is smaller too since modern GTK widget have the right behavior be default. I never did locate the cause the error that Msearch used to report, but it is gone now. I suspect it was caused by the deprecated GnomeIconTheme under GNOME 2.5+. I am very happy to see my emblems again.
I also updated the open files behavior to use the default app instead of a nautilus view so that it plays well with Nautilus.