The Rambam and the Ramban lived 1 to 2 hundred years after Rashi, so they must have been contemporaries of at least some of the Baalei Tosfos. Is there any record of written correspondence between them and the Baalei Tosfos?
The Ramban wrote a letter to unnamed French rabbis in defense of the Rambam whose books were being banned at that time. "French rabbis" is how he generally refers to the authors of Tosafot (e.g. beginning of Pesachim).
The letter is numbered 2 in the first volume of Kitvey Haramban (published by Mosad Harav Kook). The letter is also available online here but the source isn't indicated.
This is the line where he first addresses the recipients of the letter:
רבותינו הצרפתים, תלמידיכם אנו ומימיכם אנו שותים
The Ramban was a fairly close friend of Rabbi Yechiel of Paris. Rabbi Yechiel was one of the Baalei Tosafos, of the later generations. I believe Rabbi Moshe of Coucy, who compended the Tosafos Tuch (which forms the bulk of the tosafos printed alongside the gemara), was his student. (Based on a number of historical and biographical sources.)
In addition, the Ramban was strongly opposed to the ban of the Rambam's sefarim, a controversy involving several of the Baalei Tosafos of that generation.