I was convinced that there was some bug in DNS cache server too.
Tired of weird random DNS misbehavior, i've started to sniff some traffic and voila, i was simply being dumb from the beginning: Every DNS query that was over the 512 byte limit cannot be transfered using normal UDP DNS packets.
It MUST use TCP communication with the name server instead, or the name will never resolve. So, the dumb part was that my firewall rules were blocking direct access to TCP port 53 on the router... Now everything seems to be normal again!
TL