Have you ran the following from outside your network?
telnet publicip 25
Does it return any output? If it does try to manually see if the server is accepting mail by doing a
HELO myhostname
MAIL FROM:
externaladdress@something.com
RCPT TO:
internaladdress@myserver.com
DATA
test
.
It should show that the message was accepted. What is the firewall you are using? If it is an ASA you may need to configure it to allow ESMTP....