Попросите их поместить сборки MySQL в GAC. Это распространенная проблема со сторонними базами данных и Medium Trust.
Я добавлю, что вам придется сладко поговорить с ними. Им нужно будет доверять программному обеспечению, которое они будут устанавливать, чтобы не разрушать их серверы. Поэтому вам нужно объяснить, что это установленное программное обеспечение, и указать URL-адрес сайта.
Другой вариант - заставить их слегка изменить состояние зоны доверия. Это выглядит немного более подозрительно, но это не подразумевает прикосновения к GAC.