When attempting to telnet postfix from a different host in the same LAN through the FQDN (and thus the LAN's public IP), the following error occurs:

root@mailer:/var/log# telnet mail.domain.com 25
Trying 1.2.3.4...
telnet: Unable to connect to remote host: Connection refused

Other services can be reached from the exact same host, however:

root@mailer:/var/log# telnet mail.domain.com 22
Trying 1.2.3.4...
Connected to mail.domain.com.
Escape character is '^]'.
SSH-2.0-OpenSSH_6.0p1 Debian-4+deb7u1

To make matters more intriguing, Postfix can be accessed from outside the LAN:

nunos-mbp:mailog nzimas$ telnet mail.domain.com 25
Trying 1.2.3.4...
Connected to mail.domain.com.
Escape character is '^]'.
220 mail.domain.com ESMTP Postfix (Ubuntu)

To sum thing up:

a) Postfix (running on 10.10.10.4 / mail.domiain.com) refuses connection from a host in the same LAN (10.10.10.2), but only when queried through the FQDN (mail.domain.com)

b) mail.domain.com accepts connections to other services (but Postfix) from 10.10.10.2

c) mail.domain.com accepts connections to all services, including Postfix, from the outside world

If it were a firewall issue, then I believe it would not be possible to connect to any service from 10.10.10.2 through the FQSN / public IP. It ought to be some missing parameter in Postfix, although I haven't found any clear pointers so far.