Relying on this Microsoft signing service for more than one or two releases would be a mistake in my opinion. However, I realize that setting up your own CA is an expensive and risky option. Have you tried approaching any existing CAs to see if they would be willing to manage a generic Linux root cert? StartCom in particular would be a good one to talk to, since they have their own Linux distro.