Jun 14 06:21:19 auth: Error: od[getpwnam_ext](john): No record for user

I fixed this with the help of Apple Support (it had to be escalated to a senior tech). Here's the solution:

• My DNS was, in fact, correctly set up (and yours must be as well before any of this advice will work for you).
• Mavericks Server relies heavily on Open Directory and, as such, you must never do the any of the following three things once you have turned OD on:
  1. Never change the FQDN of the server. If you create it with server.example.com then that is its name. Period.
  2. Never change the IP address of the server and definitely never change or move your subnet.
  3. Don't expect any email address assigned to a Local User to work. All users receiving email must be Local Network Users preferably with the Home Folder set to "None - Services Only".
• Lion Server relied more on File Sharing and that's why email directly assigned to a Local User tended to work. In Mavericks, however, you will run into permission problems because whomever you are logged in as is the owner of whatever you create, including the file systems of other users you create. I've discovered that when setting up a Local User you need to place an email address in the appropriate field just the same. So, put something generic in that field that you have no plans on using. I set mine to ServerAdmin@example.com since I never use it (and it happens to be my "User Name", as opposed to my Full Name).
• So, if you run into this error in your mail server error log you will be strongly advised to destroy and recreate your server's Open Directory (even if some of your users are Local Network Users) - not a problem with a small test system but a big headache if you've got 500 users. Doing this makes the problem go away very quickly.

This took me quite some time to figure out and during the process I learned some really valuable things (Thanks to others in this community, especially Mr. Hoffman). These include:

• Make the OS XServer's DNS private/internal and let your domain registrar supply the external nameservers. You will have to edit their DNS SOA interface which is always fun.
• Create a private DNS that you don't expose to the internet - i.e. don't open Port 53 on your router. And set that machine's System Preferences > Network Preferences > DNS Server to 127.0.0.1. This is important as the server itself needs to know that it's the server. Further, don't use a 192.168 subnet. Use some subnet in the 10.0 group instead. I can't explain why but i had no end of headaches with my internet connection until I changed it.
• Use a static IP. I already knew this and I've been using it but I can't imagine how much more difficult this task must be using a dynamic IP. I can't stress this enough!
• Don't bother with any other task until you can prove your external and internal NS are functioning correctly.

Hope this helps.