First: Make Teredo an ISP service, by strongly binding it to the ISP: teredo server, teredo relay and addresses from the ISP. That way, ISPs have an incentive to deploy Teredo / Miredo infrastructures: help their own customers (instead of helping random people accross the Internet). This way, we would no longer have the 2001:0: teredo addresses, but ISP addresses like 2001:888:.
Second: Change Christian Huitema's Teredo protocol so that one teredo instance on a LAN can serve as a gateway for the other device on the LAN. I think one of the things thas to change, is the teredo addressing. See here for the current addressing:
|Bits||0 - 31||32 - 63||64 - 79||80 - 95||96 - 127|
|Length||32 bits||32 bits||16 bits||16 bits||32 bits|
My suggestion is to swap the two right hand parts ("Obfuscated UDP Port" and "Client Public IPv4"). Goal of this swap is that the last 16 bits can be freely changed, and thus used as addresses for other devices on the LAN. I guess those addresses can be assigned via RADVD or DHCPv6. The Teredo client would thus become a IPv6 gateway. The advantage is that devices on the LAN that can do simple IPv6 but not Teredo, will now be IPv6 connected to the Internet.
Third (and this is Microsoft-Teredo-only, not Miredo): Microsoft, please enable Windows Vista (and Windows 7?) to actually *use* Teredo IPv6 in the application layer. Now, a Vista machine will have IPv6 connectivity, but typing ipv6.google.com in the web browser will result in an error; apparently Windows won't lookup or use the IPv6 name & connectivity.
Fourth: modem suppliers should specify whether their modems let pass Teredo traffic. Just like the modem suppliers tell whether their modems let VPNs pass.