KB01120905 What is the general procedure for clearing outgoing mail problems?
Without knowing what the problem is, you can clear most stuck messages with the following procedure:
Pause the outbound router
You can do that by selecting "Active Connections" in the tree view (left hand pane) of the console then right-clicking the "Mail Router (Out)" entry in the list view (right hand pane) and choosing "Suspend" from its context menu.
Expire the dynamic cache
You do that via Console | Options | Outgoing Mail | Delivery Options tab | Advanced Routing Tables | Dynamic Routing Table.
Select each entry in the table in turn and click on the "Expire Selected Records" button to remove all the records.
Clear host assignments
In the tree view of the console, select the "Outgoing Mail" object then choose "Clear Host Assignments" from its context menu.
Restart the outbound router