Il a eu quoi ? à enjoliver la correspondance.
donc pas d’accord avec la correspondance qui n’est pas le COD.

Bonjour,

J’ajoute la confirmation  (si besoin est) et les exemples du Bon usage actuel (§ 951) :

« Avec avoir à comme synonyme de devoir , le participe est le plus souvent laissé invariable : La contrainte qu’elle a eu à subir (Green, Adrienne Mesurat, p. 166). — Quelque course que précisément il avait eu à faire (Gide, Faux-monn., p. 100). — L’immensité des espaces qu’elles ont eu à vaincre et traverser (B.-H. Lévy, Dern. jours de Baudelaire, p. 172). Cependant, des auteurs ne répugnent pas à rapporter l’objet direct à eu  : Toutes les difficultés qu’il eût eues à surmonter (Stendhal, Chartr., xxvii ). — La première lettre de ce genre que j’ai eue à écrire (R. Rolland, Au-dessus de la mêlée, p. 69). — Tous les blessés que j’ai eus à traiter (Duhamel, Pesée des âmes, p. 178). »

Le verbe « avoir » n’a pas ici de COD, pour la simple raison qu’il n’est pas utilisé comme verbe transitif mais comme auxiliaire modal introduisant le verbe « enjoliver » (j’ai à enjoliver une chose, je dois enjoliver une chose, je peux enjoliver une chose, je vais enjoliver une chose…).
* Il n’a donc pas un COD postposé qui serait « à enjoliver la correspondance ».
* Il n’a pas davantage un COD antéposé qui serait « la correspondance » (ou « que » mis pour « la correspondance »).
Un auxiliaire, même s’il est lui-même conjugué avec l’auxiliaire avoir (il a eu), n’a pas de COD, et n’est soumis à aucune règle d’accord.
Si les citations de Stendhal et Duhamel sont discutables dans le sens où « avoir » pourrait éventuellement être un verbe transitif direct (avoir des difficultés, avoir des blessés), celle de Rolland (avoir une lettre) est obligatoirement une simple faute de français.
En fait, en dépit de tolérances anciennes et artificielles, on considère logiquement ces phrases comme des phrases grammaticalement fautives quand il est évident que le syntagme antéposé est COD du verbe à l’infinitif (surmonter des difficultés, écrire une lettre, traiter un blessé) et non du verbe transitif « avoir ». Le principe du livre « Le bon usage » étant de lister autant les usages agrammaticaux que les usages grammaticaux, vous ne devrez jamais le considérer comme une grammaire.

Le Bon usage est non seulement une grammaire, mais il est une des meilleures ; pour beaucoup, il est même  la meilleure.

Le Bon usage (Grevisse, Goosse) signale tout ce qui « n’appartient pas au français régulier »,  par le symbole ° .

Concernant  l’accord de eu suivi d’un infinitif introduit par à, d’autres grammaires – et non des moindres –  vont dans son sens. 

Il en est ainsi  du  Grevisse de l’étudiant, CAPES ET Agrégation Lettres, de Cécile Narjoux, préfacé par  Mary-Anncy Morel. 
C. N. a été membre du jury de l’agrégation externe de Lettres modernes (présidente et membre de l’agrégation de grammaire)  et du jury de l’agrégation de Lettres classiques. 
M.-A. M. : agrégé de grammaire,  professeur émérite à la Sorbonne (1983-2009), directrice de l’Information grammaticale.
Page 576 :  « Eu, laissé et donné suivis d’un infinitif introduit par à peuvent s’accorder ou rester invariables  parce qu’il est possible de rapporter le complément d’objet direct à l’infinitif ou au participe.
Les affronts qu’il a eu à subir est plus fréquent que qu’il a eus à subir. »
N.B.  1. Cette fréquence supérieure  (le Bon usage l’indique : cf. ma citation de cette grammaire) ne signifie pas, bien évidemment, un caractère correct exclusif, au contraire.
2. Citation : Le gras est dans le texte.

Etc. 

C’est assez étonnant, ils ont modifié ma réponse (la 4e dans l’ordre de parution), ils ont supprimé le commentaire insultant de Joëlle, et ma réponse à son commentaire.

J.-J. J.