They charge a fee to get a certificate that you can use to submit binaries to be signed with the Microsoft signing service. If you're a user of a distribution you won't have this problem, because distributions have already paid and have a hack "shim" which effectively enrols the distribution's own keys into the trustdb. But if you wanted to make your own distribution you would have to pay.
This isn't actually true, is it?