Скорее всего, сервер резолвит DNS-имя клиента по IP-адресу - и не может, поэтому ждёт тайм-аута.
Второй вариант: Вы пытаетесь запихнуть письмо на главный релей, а он не отвечает. И после тайм-аута - письмо засовывается запасному релею.
Третий вариант: На сервере работает GreyListing.
Уточните, на каком компьютере Вы выполняете функцию mail; и к какому серверу коннектитесь.