Recently had a request for help from a client who could not add a new user to their Open Directory. I Googled around for a while before finding an answer that was easier than rebuilding all of Open Directory and its accounts.
Error: eDSRecordNotFound
Solution: Get Open Directory to restart by turning the SSL option on, then off again.
After this, the user could be added normally. The error did not occur.