I pointed my users at a webpage that explained the two command lines needed on Windows to enable Teredo, and now Windows was speaking IPv6 just fine.
I recommend you consider setting up a Teredo relay on your server.
What will happen with traffic between your server and the clients using Teredo is that packets from the server will be routed over your 6in4 tunnel to the HE tunnel server. From there it will be routed to the closest Teredo relay and then travel through a different tunnel to the user.
This means you have no control over which Teredo relay is being used, it could be any third party relay. In practice I guess it will always be one within the HE network, but in my experience the Teredo relays is the least stable part of the services HE offer. I don't think it will take much for you to provide better reliability than the HE Teredo relays.
In addition by running your own Teredo relay, there will only be one tunnel between your server and your users rather than two.
The Teredo relay shouldn't be announced to the rest of the network such that it will only be servicing your own network. Running a Teredo relay does require a public IPv4 address, but it is no problem to be using a dynamic IPv4 address for that. For Teredo it is only the server and client IPv4 addresses that really matter.
