If you have ongoing contracts with the individuals then the lawful grounds for processing would be “contractual obligation” rather than consent. So, you would only need to provide them with the relevant information via your privacy notice/notices.
Checking the identity of the data subject is one of the first steps when dealing with a DSAR so waiting till the last day to confirm the identity of the requester to get the 30 days period “reset” would most likely be considered abusive. So my advice is to check the identity of the requester as soon as possible in he process. Please consult the “Data Subject Access Request Flowchart” which is part of the “ DATA SUBJECT ACCESS REQUEST PROCEDURE” to see how a DSAR flow could look like.
As regards to the form is not a compulsory requirement to use a specific template although is advisable to do so as the requests would be handled much easier and in a consistent way.
If you have just one website which collects data from users you should list both controller entities with their registered address so the users can know who are the data controllers. Is not absolutely necessary to mention the VAT number the contact details should be enough.
This is up to you basically. Usually companies choose to notify their customers about changes in their T&C or relevant Policies, so this is more like a best practice than an obligation.
You just need to make sure that the Privacy Policy/Notice is easily available to all your customers.
If you are offering goods and services to individuals in the Union then at least some GDPR requirements would be applicable to your company as well in terms of processing the data of your customers.
However, if you just provide a service other travel companies this means you are a processor and your reasonability will be limited to certain extent.
The document you are looking for is the “Supplier Data Processing Agreement” (especially article 4.Reliability and Non–Disclosure) which can be found in folder 6 of the EU GDPR Documentation Toolkit https://advisera.com/eugdpracademy/eu-gdpr-documentation-toolkit/