Mail not working

For some reason, I cannot use mail. Nameserver looks ok, ping to the server is ok, mailserver runs fine, but I can’t send mail. I restarted the mail-daemon, restarted the complete server, but nothing.

:-/

Update: I tried about everything: I’ve reset (powerdown/powerup) all network hardware, restarted the PC’s, disabled all anti-virus/firewall software, but I can not send or receive any mail.

Update 2: I’ll be damned. I restarted this PC *AGAIN* and now it works. Windows XP rules. NOT!