Hi Pana,
Hmmm... Are you able to check your mailbox storage in your Microsoft account to see if it still shows as full?
If you still get a postmaster bounce after deleting 500 emails, your mailbox is likely still over the limit. With around 259,000 emails, removing a small amount does not free enough space. It blocks sending and receiving when storage is full, so messages continue to fail. You need to delete a larger number of emails, including large ones with attachments, then empty Deleted Items and Junk since those count toward storage. After that, wait a short time for the mailbox to sync, then send a test email again.