Если site.ru - это доменное имя сайта, то кто отвечает за сервера, на которые указывают записи NS этого доменного имени?

Именно на них нужно сделать записи MX, указывающие на почтовые сервера.