I had the same problem after upgrading from Server 3 to Server 4.
I figured out that mail is working fine when I was editing the main.cf ( /Library/Server/Mail/Config/postfix/main.cf ) and comment out the following line as so:
#smtpd_require_virtual_map = yes
The hint was given here: Mail service on the OS X Server 4.0 works only locally
But this is not a proper solution 'cause every time the Server App receives an update or the Mail Server is updated Server 4 is updating the main.cf also and is un-commenting that certain line so that the mail delivery breaks again.
So, I had to fix this.
Here is the solution which worked for me.
1. Start the Server App. And make sure that Mail and DNS services are up and running.
2. Go to "Mail"
3. In the domain section delete all domains except the one your server is listening to. Let's call it "mymaindomain.com". This domain must be managed by the DNS service on your server.
4. Go to "Accounts" > Users. Doubleclick any user of your decision and have a look on his/her mail address. You should see only one mail address ending with "@mymaindomain.com".
5. In my case I was using the Mac shortnames as the account names. That caused trouble 'cause I want to have the mail addresses in the way "prename.surname@mymaindomain.com". So I had to rename the account names for each user to prename.surname. (there are some "how tos" by Apple to get this done whith keeping any data)
6. Reboot the server. I preferred to turn the server completely off... and on.
7. Go back in the Server App > Mail.
8. In the domain section click on "+" to add a new domain. In the next window type your additional domain in Domain line - let's say "myseconddomain.com". In the section below you should now enter some members of "myseconddomain.com" and validate the mail addresses that are created for the users you specified. Then click on "create" ... The Server App will now create all the files postfix needs to run virtual domains.
9. You are done!
It seems to be necessary to create the mail addresses that way and NOT in the Accounts / Users section.
Robert