users.....mail-server

Можно.  Сначала надо найти mail exchanger домена:

   host -t mx domain.com

Потом подконнектиться в 25-му порту этого mail exchanger'а:

   telnet mail-exchanger.domain.com 25

Сказать ему

   HELO my.hostname.com
   MAIL From: existing-mbox@existing.domain.com
   RCPT To: user1@domain.com

Если после этого он скажет, что адрес user1@domain.com проверен и такой ящик существует, значит такой ящик действительно есть.