O verbo deixar tem um alto grau de polissemia e, portanto, é natural que, entre os seus vários usos sintáticos, possam ocorrer certas interferências. No sentido de «dar, entregar», os dicionários de verbos (p. ex. Dicionário Houaiss) indicam que o destinatário é marcado como um objeto indireto, isto é, como um complemento introduzido pela preposição a, o que faz de «deixei à Joana recado à Maria» uma frase indiscutivelmente correta.
No entanto, há dois pontos a considerar:
1. Sobre a aceitabilidade de a preposição com poder substituir a na frase em questão, observe-se que, se o objeto direto for realizado por uma expressão nominal que refira uma pessoa, é correto empregar com, sendo o complemento preposicionado interpretável como o mesmo que «na companhia de»:
(a) « Também pensara que o menino se acabasse, morresse. Voltando para o Araticum, quis trazê-lo para junto de si. A mulher metera na cabeça deixá-lo com o padre. E que ele ficasse por lá mesmo» (José Lins do Rego, Pedra Bonita, 1938, in Corpus do Português).
Esta construção pode ser transposta de modo a realizar o objeto direto com um substantivo de denotação abstrata e o objeto indireto com um substantivo concreto aplicável a pessoas:
(b) «O senhorio perseguia-o; ele fugia e deixava com a mulher o encargo de explicar os atrasos» (Lima Barreto, Clara dos Anjos, idem).
Não se pode dizer que esteja errado este uso, não atestável em textos de Portugal a partir da consulta do Corpus de Português. Diga-se, portanto, que é um uso que a escrita literária não abona frequentemente, mas que a sintaxe e semântica do português em geral podem abranger e tolerar, porque o valor «na companhia de» pode ser entendido como metáfora, uma vez que, pragmaticamente, «deixar algo com alguém» é «deixar algo a alguém temporariamente».
2. Ainda quanto à frase «Deixei à Joana recado à Maria», observe-se que também é gramatical dizer/escrever «deixei à Joana recado para a Maria» e até «deixei recado à Joana para a Maria» de modo a distinguir claramente o beneficiário do recado («para a Maria»).