We recently purchased a domain name, strictly for the purpose of having it for email. We can send from it normally and receive it in a timely manner. However, when replying to that email, it will take a couple of days before we get a non-deliverable message. DNS we think is fine and we're not blacklisted at all. We're using Godaddy as our registrar and Outlook 2003 as our client.
Not sure what else it could be. All help is appreciated!