Zunächst mal sollten alle Aktionen, die Du jetzt online machen willst, von einem definitiv sauberen (nicht kompromittierten) System aus vorgenommen werden (siehe auch Hinweis von lexlegis).
Zu dieser Frage
Sollte ich besser das Microsoft Konto löschen und das E-Mail Konto ebenfalls?
kann ich Dir keine pauschale Antwort geben. Es kommt schließlich darauf an, wie wichtig diese Konten für Dich sind, wofür Du sie bisher nutzt und ob Du so ohne Weiteres darauf verzichten könntest.
Auch wenn Du Dich dazu entschließt, ab sofort mit neu angelegten (alternativen) Konten weiterzuarbeiten, solltest Du die bisherigen Konten jedoch auf keinen Fall löschen, da diese anschließend ja für Dich nicht mehr nutzbar sind, ein evtl. Angreifer diese dann aber (u.U. nach einer Wartefrist) für sich registrieren könnte.
Wofür benutzt Du denn z.B. das Microsoft-Konto?
Sicher ist, dass sich jemand über eine IP Adresse in Warschau in mein Microsoft Konto eingeloggt hat.
Dies hat Microsoft Dir mitgeteilt? (Oder wie hast Du davon erfahren?)
Allerdings war mein Passwort noch aktiv.
Meinst Du damit, dass der Angreifer Dich (noch) nicht ausgesperrt hatte?
Gleichzeitig wurde meine Kontaktliste gel?scht. Ebenso mein gesamter E-Mail Verkehr.
Wo wurden diese Inhalte gelöscht? Online (auf dem Mailserver) oder offline (im Outlook auf Deinem lokalen PC)?
Outlook habe ich von meinem Rechner und von meinem Handy gelöscht.
Warum?
Hast Du auch daran gedacht, Anzeige bei der Polizei zu erstatten?