Проблема вилізла в декількох різних місцях, коли вони різко всі перестали різолвити. Так що - libresolv, а не nslookup конкретно.

Кароч, воно виглядає так, що якщо у хоста(-ів) є multipath, то треба бути готовим до будь-яких несподіванок. Тому що далеко не всі софти вміють bind to specific interface / address й глюки можуть вилазити будь-якої миті :-\