Meanwhile I found the problem: it is dynv6.com itelf :(
Their 3 nameservers are not all responding with the same answer, in my case #2 claims to not have a AAAA record while #1 and #3 show the correct ip. It seems though I'm by far not the only one, and that this is not a new problem: https://community.dynv6.com/t/the-ns-1-3-dynv6-com-not-always-updated-with-my-public-ip-address/1107
I switched to another ipv6 dyndns provider, and all seems well now. So stay away from dynv6.com I guess. A shame really, as they have a really nice and intuitive UI, and seemingly also are the only ones that handle a ipv6-prefix for a whole zone...