This situation seems a lot more complicated than just using the sign tool.
On further reading it appears as though, as you say, to have your game trusted automatically by Windows, you need to subscribe to a third party certification authority. Doing this though is rather expensive and I imagine most of us (including myself) cannot afford to do this, there also appears to be no reasonable or accessible alternative on a Windows system for this.
Using the sign tool is still a good step as it does "sign" the application for your Windows install, and apparently, if this is done and the application gets enough downloads, Microsoft may eventually consider the application as "safe".
It's quite annoying that there isn't a good solution to this problem for Windows. I will update the post to reflect this.
I think there needs to be some kind of option for this that is accessible to small developers.