I see you're not using a relay. Make sure you have a reverse DNS (PTR) record and an SPF record in place for the mail server. I had this same problem, but I could flush the mail queue every so often and a small handful of the emails would go out. Turns out most mailservers will "greylist" suspicious senders.
Basically, the receiving server waits to see if you try again, and will allow the message through the second try (most spambots don't retry).
For receiving, have you forwarded all the necessary ports? Try to telnet port 25 or 465 or whichever you are using. Sometimes the ISP will block port 25 to reduce spam.