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.