When attempting to send a message which is too large for your mail server, it may become stuck in the outbox, unable to delete it, because Outlook says it has already started to send the message.
If this happened to you, there are two things to try...

Solution 1

Try setting Outlook in offline mode:

1. In the menu, click File, then Offline
2. Wait about a minute or so, then close and reopen Outlook
3. If everything went well, you should now be able to delete the message from the outbox, or at least, move it to another folder before attempting to delete it.
4. When this worked, disable offline mode: click on File in the menu, then again Offline
5. Finally, restart Outlook and everything should be well again.

If this solution didn't work for you, then the below one might just do the trick; it's a bit more complex, though.

Solution 2

Another solution is to change the default delivery location. This way, Outlook will stop sending messages from the current Outbox, thus enabling you to delete the oversize message.
The following steps are the same for Outlook XP and 2003, although the menus may be a little different:

1. First, add a new, empty PST datafile, by using the File, New, Outlook Data File menu. Type in a name (doesn't really matter which name), and click Save. If you want to be tidy, save the file in a location you have quick access to (rather than deep down into your windows profile), e.g. My Documents.
2. You will see a new window, prompting you to enter a name, selection Compression, and fill in a password. It's recommended to change the name to something easy to recognize, but it doesn't really matter since this is only temporary, it's not required. The new PST will appear in the tree to the left.
3. Now change the delivery location: click Tools, Email Accounts. Select View/change existing email accounts, and click Next.
4. Set the Deliver new email to the following location to the name of the PST you just created, then click Finish.
5. You'll be prompted to restart Outlook, do so.
6. Upon restart, find the Outbox in the original PST, where you'll find the message again. Only now, you should be able to delete the message.
7. Repeat steps 3 to 5 to set the delivery location back to your original PST.
8. Optionally: if you have received new messages when the temporary PST was the delivery location, you need to move these messages to your own original (and now default delivery location) PST. Don't forget to check this because when closing and removing the temporary PST, you'll lose those messages!
9. Finally, remove the temporary PST by right-clicking its name in the folder tree, then choosing Close personal folders
10. As a last step, if you want to be tidy, you can remove the PST file using Explorer (if you remember its location, that is).