It's good to remember why there is a review in the first place -- users of the Appexchange want confidence that they can use the solutions listed there safely. Obviously nothing is perfectly secure, but the appexchange offerings go through security review to provide a (hopefully uniform) level of assurance.
Therefore if there is a composite solution in which the user needs to register with a third party and provide some personal information (e.g. credit card, email address) in order to use the offering, then the security review team will also test the third party service at the application level, because it is part of the overall solution. Note that I didn't discuss whether code was going from Salesforce to the third party or vice versa. This is not a legalistic question -- if Salesforce customers need to trust the external service as part of the offering, then it is in scope for review.
This does not necessarily mean that the third party service will need to be tested as part of each offering -- some third parties are used in multiple appexchange offerings and there is no need to test them each time a new integration listed. If you want to partner with a third party, please ask them if they have been through this process already (and if they are willing to go through it for the sake of your integration).
On the other hand, take a free service such a mapping api for which the user does not need to register or provide confidential information. The provider of the api does not come in scope for the review (you will still be asked to use SSL when making a connection with them).
If Salesforce stores user data such as account names with a third party, then certainly the third party will be tested, because users of the offering need to be able to trust that their data is protected on the third party's servers. If a third party stores credentials to log into Salesforce on behalf of a user, then the third party will be tested in order to protect the credentials.
One thing that is irrelevant to the scope of the security review is the underlying business or ownership structure. It does not matter if company X hires a subcontractor to make an integration on the appexchange, or uses their own developers to do it, or if a third party having no relationship whatsoever to company X decides to make their own integration using company X's public APIs. The user's data does not become more or less vulnerable to being leaked from company X because of the ownership structure of the integration.
So try to use common sense and keep in mind that the purpose of the security review is not to force developers to jump through hoops, but to protect the end user of the appexchange. If you have more questions, please book an office hour and a member of the review team will clarify the scope.