Apparently dnsjava's Cache.flushSet doesn't flush negative answers.
As a workaround use Cache.flushName instead.
Make this beta6.
Back to snapshot version.