Presbyter Adeodatus here is most probably the same as the addressee of other Ennodius's letters, see PCBE, Italie, v. 1, Adeodatus 8 (also [1503], [1505]). It is possibly also the same person as the Presbyter Adeodatus present at the council of Rome in AD 495 [661] and the Presbyter Adeodatus present at the council in Rome in AD 502 (PCBE Italie, v. 1, Adeodatus 7, 9). It is impossible to say with precision whether we have here one, two, or three different Adeodati.
Faustus mentioned in the letter is the praetorian prefect Anicius Probus Faustus (he held the prefecture from 509 to 512), see PLRE II, s.v. Anicius Probus Faustus 9, 454-56. His son, mentioned but not named by Ennodius, was Rufius Magnus Faustus Avienus, later also the praetorian prefect of Italy (from 527-28).