Android - Corporate Exchange Email Won't Send (stuck in outbox)

The first thing I'd suspect is that a database used by the Email app is corrupted. To fix this, you need to go to Settings -> Applications -> Manage applications, find the Email app, and clear the data for it. (If you see anything like "Email Storage" be sure to clear the data for that as well). Then re-add your account and see if that helps.

If that doesn't work, I recommend asking your company's IT department if they have changed any settings for the Exchange server recently.