Domain of sender address does not resolve (in reply to MAIL FROM command)

When sending out emails with postfix I sometimes get this error:

451 #4.1.8 Domain of sender address <[email protected]> does not resolve 
(in reply to MAIL FROM command)

The domain mydomain.tld is resolvable though, meaning A, MX, PTR records are set properly.

However, the sending server does have a different domain anotherdomain.tld but it is allowed to send emails from mydomain.tld since I set the MX records of mydomain.tld to anotherdomain.tld. The envelope from of the problematic emails is [email protected].

Is there some other dns entry I have to set?

Or how else could I solve the problem? (I would like to keep the server structure though)

The problem is simply one of DNS resolution. Either the receiving MTA doesn't have reliable DNS resolution, or your DNS servers are flaky. Without knowing what domain mydomain.tld actually is, it's impossible for anyone to determine whether the latter is the case, but the more recipient domains who are sending you this error, the less likely the former becomes.