es gibt keine "offiziellen" Blacklisten, du könntest aber natürlich mal die größten stichprobenweise testen. Ich tippe eher darauf, dass dein Mailserver schlecht konfiguriert ist. Wenn web.de die Mails nicht annimmt, dann sollten sich entsprechende Einträge in den Logs des Servers finden. Einfach löschen werden die die Mail nicht, denn dies verstößt gegen das Gesetz (Unterdrückung von Nachrichten).
Wichtig ist, dass dein Mailserver sich mit seinem FQDN beim anderen Server anmeldet und seine IP-Adresse sich auch wieder auf diesen Hostname auflösen lässt. Hilfreich, aber nicht notwendig, ist, wenn der Server auch noch als MailExchange-Eintrag in der Domain eingetragen ist (hier sollte der Server IMHO als A- und nicht als CNAME-Eintrag vorliegen). SPF-Einträge können hilfreich sein, werden aber, wenn nicht vorhanden, im Regelfall ignoriert.
Ich hatte bisher nur einige wenige vereinzelte Fälle, bei denen ein Server versehentlich auf eine Liste gekommen ist, das konnte aber immer nach kurzer Absprache mit den Anti-Spam-Abteilungen von web.de, yahoo und co. wieder geklärt werden.