6to4 is known to be unreliable, and Teredo is even worse. When you communicate between 6to4 and Teredo you get all the problems of each combined plus a few more due to complex interactions between the protocols.

Thus it may come as a surprise to you that the answer is: Yes, you can get reliable communication between 6to4 and Teredo.

Both protocols suffer from the same main problem. They rely on third party relays which are underprovisioned and due to their third party nature come with no SLA.

Teredo uses one relay for both directions. 6to4 usually uses two for different directions, but due to the triangular routing in Teredo you end up depending on three 6to4 relays rather than just two. That is a total of four third party relays which you will be depending on - all of which must have enough capacity for your traffic.

But you don't have to rely on third party relays. You can set up your own relay.

Setting up your own Teredo relay

The Teredo relay is the simplest to set up, and it happens to be the most important to your scenario. A Teredo relay needs a single UDP port on a public IPv4 address. Thus you should not deploy the relay on the LAN behind your D-Link router. You should avoid having any 6to4 relay/gateway on the path between your LAN and the Teredo relay. Thus you should not deploy the relay outside the D-Link router.

In short you need a Teredo relay on the D-Link router to make connectivity work reliably. If the D-Link cannot run a Teredo relay, your best option is to replace the D-Link router with a router which can run a Teredo relay. In my experience it will work reliably if you use a Linux machine with Miredo configured in relay mode for the router.

Deploying your own Teredo relay on the D-Link router would not only mean that you no longer rely on a third party Teredo relay. It will also give you a native path between your Teredo relay and your LAN, thus you avoid two of the three third party 6to4 relays as well.

What's left

You would still be relying on a single third party 6to4 relay. A Teredo client need to choose which Teredo server it will be using. The two Teredo clients I know of each have a default configured which will be used if you do not change the configuration yourself. The network path from the Teredo server to your D-Link router will have to pass through a 6to4 relay.

So what you need to do is to choose a Teredo server with access to a reliable 6to4 relay. Ideally a 6to4 relay should be configured on the machine running the Teredo server.

Is this a recommendable configuration?

Installing a Teredo relay on your router is definitely a reliability improvement as long as your router has a public IPv4 address. It will give a significant reliability improvement for any communication with Teredo users, and it will not have any impact on other communication. This is true regardless of whether your router is doing 6to4 or native IPv6.

Using 6to4 on your LAN is however not recommendable as many networks have not installed any 6to4 relays. Hosts on your LAN would often face problems communicating with hosts with native IPv6.

Using a Teredo client is not recommendable either due to all the same reasons that 6to4 isn't. However there are a few cases where Teredo can be useful. Most importantly a Teredo client can connect to hosts on the LAN behind your router (assuming your router has a Teredo relay). And sometimes I have come across CGN deployments working so poorly that Teredo through the CGN is more reliable than TCP through the CGN.

Are the clients' prefixes being manually assigned? Usually they should automatically find the router via Neighbor Discovery Protocol (during which the router sends out advertisements and assign them prefixes automatically), but it sounds like that step might be missing.

Additionally, the router advertisement should be including its link-layer address as an option in the ICMP header of the router advertisement. If this field is missing, the client won't know how to send data to the router. It sounds like this could be the case. The client doesn't know how to reach the router, until it sends out the Neighbor Discovery message and it receives an Neighbor Advertisement from the router (with the router flag in the ICMP message set).

To include the source link layer address in your router advertisements, add the following into your radvd.conf

AdvSourceLLAddress on;