I'm afraid Wobblington's answer is incorrect. It doesn't matter who holds the data. What matters is who controls it.
Under GDPR, a data controller controls the data, i.e. they decide what data is held, how long it is held and how it is processed. GDPR also recognises the concept of a data processor - a company that processes data on behalf of a data controller. If a data controller uses a data processor the data may exist only on the data processor's systems, but the processor only processes it in accordance with instructions from the controller. In this situation the data controller is still responsible for that data and must deal with any SARs. They must respond to SARs themselves. They must not direct the subject to the data processor.
So it depends on the relationship between the two companies. Given that the first company (let's call them ABC) wrote to you, it is reasonable to assume they are a data controller. The question is whether XYZ is an independent data controller, supplying data to ABC, or a data processor, processing data on behalf of ABC.
If XYZ is an independent data controller, ABC must respond to your SAR by providing any information they hold about you. If they delete all your information from their systems as soon as they send the letter it is acceptable for them to say that they don't hold any information. However, if they continue to hold any information they should have provided that information in response to the SAR.
If XYZ is a data processor, holding information on ABC's behalf and processing it in accordance with their instructions, ABC is wrong to direct you to XYZ. In that situation it is ABC's responsibility to provide the information in response to your SAR.
Without knowing the details, my guess from what you've written is that ABC buys lists of marketing contacts from XYZ. In that situation both ABC and XYZ are independent data controllers (although ABC may not have realised they are a data controller). So ABC should provide you with any information they still hold on you (which may be none at all - they may simply produce the letter then bin the data) but you need to make a separate SAR to XYZ for the data they hold.