Web.de E-Mail Konten gehackt?

Dracarys

Hallo liebe Foren Gemeinde,
ich möchte mein Anliegen mal kurz umreissen, damit ihr wisst worum es geht:
Gestern wurden von meinem Skype Konto aus Spam Nachrichten an alle meine Kontakte geschickt. Das habe ich nur bemerkt, da auf meinem Handy Skype drauf war, da ich Skype eigentlich schon seit Jahren nicht mehr nutze. Das Passwort war deshalb leider auch ziemlich schwach. Ich gehe davon aus das es einfach nur gehackt wurde. Keine "große" Sache.
Allerdings erhielt ich gestern von web.de (keineantwortadresse@sicher.web.de) eine Sicherheitswarnung zur e-Mail Adresse auf der auch mein Skype Konto lief. Ein kurzer Ausschnitt:
"...zu Ihrem persönlichen Schutz haben wir vorsorglich Ihr Postfach gesperrt, da unsere automatischen Sicherheitssysteme Unregelmäßigkeiten beim Zugriff auf Ihren WEB.DE Account festgestellt haben bzw. Ihre WEB.DE E-Mail-Adresse von einem sicherheits-relevanten Vorfall bei einem externen Online-Dienst betroffen sein könnte. Durch die Sperre wird der Versand von E-Mails aus Ihrem Postfach heraus blockiert, um einem Missbrauch vorzubeugen...". In der Mail wurde außerdem eine Telefonnummer für 3,99€/Anruf als Support angegeben. Erst dachte ich an eine Phishing Mail. Daher bin ich im Browser auf web.de und habe mich dort eingeloggt. Dort kam dann eben die Aufforderung zum Passwort ändern, was ich dann natürlich auch gemacht habe. Das Passwort des e-Mail Kontos ist eigentlich ziemlich sicher (über 12 Zeichen, Groß- und Kleinbuchstaben, Sonderzeichen und Zahlen) und ich benutze dieses Passwort nur für diesen Mail Account.
Also habe ich dieverse Viren Scans gemacht (Bitdefender, adwcleaner und Malwarebytes). Bis auf eine Adware wurde nichts gefunden.
Heute habe ich die gleiche e-Mail bei einer anderen web.de Adresse erhalten. Auch dort eigentlich wieder ein sehr sicheres PW. Irgendwie kommt mir das alles sehr suspekt vor. Am liebsten würde ich bei web.de nachfragen was da los ist, allerdings gibt es nirgends eine Mail Adresse von denen und 3,99€/Anruf sind dann doch ziemlich happig sodass ich erstmal über diesen Weg um Hilfe frage.
Weiß da jemand vielleicht was da los ist, bzw was ich noch machen könnte?

und Viele Grüße