Wenn du, was ich vermute, deine Mailkonto via IMAP eingebunden hast, dann kann diese Fehlermeldung sich nicht nur auf Mails in deinem Postausgang beziehen, sondern auch auf Mails in jedem anderen Ordner, die zum Server synchronisiert werden sollen.
Konkrete Vermutung:
Nachdem du das Mail aus dem Postausgang gelöscht hast, ist es in den Papierkorb gewandert. Und Outlook versucht nun vergeblich den Papierkorb-Ordner mit dem Sever abzugleichen.
Kurzum: Prüfe alle deine Ordner nach übergrossen Mails und lösche diese komplett (nicht nur in den Papierkorb verschieben)