A profile can have multiple external IDs. The required external ID is used as the username that must be used to log on. The default required external ID is DUNS. You’ve indicated that they’ve configured their required external ID to be Mutually Defined, which is an okay thing to do.
When the partner logs on, they must log on using the required external ID to be able to submit docs to TN receive and have the doc pass the security check.
The doc itself can use any single external ID, which is controlled by the doc type attribute extract configuration. If the doc type specifies that the extracted sender is DUNS, then the doc must contain the DUNS identifier. For your setup, to pass the security check, the DUNS must be for the same profile as the Mutually Defined identifier used to log on.
I assume the partner is submitting documents directly to receive. The Ezine article at http://www.wmusers.com/ezine/2002oct1_schauhan_1.shtml identifies several drawbacks to doing this.
If you want to bypass the security check, create your own entry service and submit the doc to TN by calling wm.tn.doc.xml:routeXml instead of wm.tn:receive. The only difference between these two services is that routeXml doesn’t perform the additional security check.
So, for your setup the partner must log in using the Mutually Defined identifier (and the password you assign) and the document must use the external ID defined by the doc type (the discussion so far has said it is DUNS). Having the partner use the Mutually Defined ID to log on shouldn’t be a big deal. Their docs can have DUNS and still pass the security check.