Messages stuck in the outbox, not sent even when trying Send All

Delete the .ost file @:
C:\Users\CurrentUsername\AppData\Local\Microsoft\Outlook

N.B.
1- Non-server side data will be deleted, such as previously unsent items in the outbox.
2- All outlook cached items are going to be automatically downloaded which can be as big as 200 or 400 MBs.