Hello,
Below is the snippet from the response that we receive to update/upsert a contact value from another system. Get a foreign key error on the account entity. The value is present on the account object (queried to find).

<tns:externalIDFieldName>Number__c</tns:externalIDFieldName>
            <tns:sObjects>
               <ens:type xmlns:ens="urn:sobject.partner.soap.sforce.com">Contact</ens:type>
               <ens:SId__c xmlns:ens="urn:sobject.partner.soap.sforce.com">12345678</ens:SId__c>
               <ens:Number__c xmlns:ens="urn:sobject.partner.soap.sforce.com">12329065</ens:Number__c>
               <ens:StreetAddress__c xmlns:ens="urn:sobject.partner.soap.sforce.com">47 GEORGE STREET</ens:StreetAddress__c>
               <ens:StreetAddress2__c xmlns:ens="urn:sobject.partner.soap.sforce.com"/>
               <ens:StreetAddress3__c xmlns:ens="urn:sobject.partner.soap.sforce.com"/>
               <ens:Account xmlns:ens="urn:sobject.partner.soap.sforce.com">
                  <ens:type>Account</ens:type>
                  <ens:AccId__c>12344445</ens:AccId__c>
               </ens:Account>
            </tns:sObjects>
 
<message>Foreign key external ID: 12344445 not found for field AccId__c in entity Account</message>
                  <statusCode>INVALID_FIELD</statusCode>

Please assist.

Thanks!