Mikael, Eric,Are you running Teredo relays close to your content you are using to test?
Mikael, are you able to share (privately if need be) the actual test? I'd like to look at how it works to try and see if I can see what's causing Vista/Teredo to not pick it up as much as I expect.
-- Nathan Ward