Dedibox - Plesk - Gandi et envoi de mail !

Bonjour à tous !

Suite à la désertion de mon webmaster, je suis un peu désemparé face à un problème concernant l'envoi de mail depuis ma dédibox : ils tombent quasi tous en spams.
J'avoue avoir lâché l'administration depuis que j'avais trouvé ce webmaster, et je n'ai jamais été un gros pro de toute façon.
Son départ a coincidé avec le moment où on changeait de serveur pour passer sur dedibox.

Ma config actuelle :
Hebergement sur une dedibox,installée avec Plesk 8.6.0.
J'ai laissé la gestion des DNS chez Gandi

Les scripts d'envoi de mail que j'utilisais auparavant sont les mêmes, ca fonctionnait bien pourtant chez Adviseo.

Après moult lectures sur le net, j'ai trouvé des infos sur les spf, j'ai paramètré tout ceci mais ca ne fonctionne toujours pas.

Il y a donc quelque chose qui cloche, mais je n'arrive pas à trouver quoi.
Soit un paramètrage qui manque sur Plesk, soit un conflit entre la config de Plesk et ce que j'ai mis sur Gandi...
J'ai dû louper une étape importante sur la config du plesk.

Une âme charitable et douée pourrait elle me donner un coup de main ?
Merci d'avance !

 

Pour info, ce n'est pas un site commercial mais un webzine musical.
Je peux dédommager le coup de main par quelques CDs