Письмо о подтверждении сотрудничества
 

Вы не обязаны заключать соглашение. Акцептованные вами счета являются подтверждением принятого предложения. Экземпляр CМR с отметками грузоотправителя и грузополучателя являются подтверждением выполнения перевозки на акцептованных условиях. Покажите таможне эти документы. В случае, если будут упорствовать - письменно запросите у них ПИСЬМЕННОЕ требование о предоставлении письма, с указанием причины возникновения данного требования. Должны отстать.

Добавлю: в объяснениях в таможню в подобного рода случаях можете сослаться на обычаи делового оборота. Срабатывает. :)
Никто не виноват ведь, что в нашей стране требуется 48 раз документально подтвердить взаимоотношения контрагентов.

А Вы вообще в СМР присутствуете?
А работаете правда без письменного договора на основании устных соглашений?

Да, без соглашений, зачем, если разовый агент? Ну, и конечно сумма счета меньше 5000$ :)

А на первый вопрос?
А по второму, в случае косяков как разбираться будете? Это услуга на 5000, а товару на скока?

Что касается первого вопроса, то нас нет в CMR, т.к. мы только организуем перевозку, а не осуществляем ее. Во втором случае и цена товара нас тоже мало волнует, главное оплатить услуги нашего агента, в соответствии с законодательством Рф, разумеется :)
Таможня попросила нашего клиента предоставить основание сотрудничества с перевозчиком (точно не скажу может он и грузоотправитель), а он сослался на экспедитора, т.е. на нас.

Если Вы должны были представлять интересы данного перевозчика в таможенных органах (или пытались это делать), допустим, при получении разрешения на ВТТ, то требования таможни абсолютно обоснованы. Надеюсь с законом о транспортно-экспедиторской деятельности Вы знакомы?
Как я понял, вы, как риэлторы, в договоре отражаете только "предоставление информации клиенту о перевозчике". А договор они заключают напрямую. Только в таком случае Вас может не интересовать стоимость груза и т.д.??

Нет, первый договор заключен с клиентом о предоставлении услуг ТЭО, второе соглашение с агентом (перевозчиком) и на основании нашей заявки агент перевозит груз клиента и пункта "А" в пункт "Б".
Касательно упоминания нас в транспортных документах, у меня появились сомнения, т.к. иногда мы есть, но в большинстве случаев нас нет.
Что касается закона о ТЭД, то при международных перевозках с иностранным агентом, каким образом его применять?! )))))))))))))))))

Так деятельность по ТЭО Вы ведь осуществляете на территории РФ, и Вы резидент и клиент Ваш - получатель тоже резидент.