We started to see the same problems recently on our servers (RedHat) ...
Indeed just restarting nsd seems to make the issue go away but we haven't found yet the reason. When these errors occur, it also matches with some strange logs in the access_log file.
Using nsopenssl-2.1a here ... and:
openssl-0.9.6b-32.7
RedHat 7.3