I always had ipv6 tunneling enabled on my server. One with he.net and one with 6to4. I never had any problems with them with either as a default route. Recently my server provider linode.com start supporting native IPv6, but I found out other IP addresses are not route-able through native interface. Linux is only smart enough to pick which source address to use for outgoing connection, but not so much about return path.
The solution is policy based routing with IPv6. There are two related options in kernel configure, so make sure they are enabled. If not, you will encounter an error.
First install iproute2 and add a new route table.
echo "200 to4" >> /etc/iproute2/rt_tables
Then you can add source based rules and routes to this table.
ip -6 rule add from 2002::/16 table to4 ip -6 route add 2002::/16 dev 6to4 table to4 ip -6 route add default via ::126.96.36.199 dev 6to4 table to4
One thing I am still not sure is whether to delete the 2002::/16 from main route table.
ip -6 route del 2002::/16
I think this can solve some stateful firewall problem, but not necessary.