First, check for updates to Office.

This article applies to Office 2000, but may be work a look:
http://support.microsoft.com/kb/214384

Link to some other possible solutions:
http://help.lockergnome.com/office/emails-programs-ftopict714896.html

Tried the 1st one already. Did not work

Tried the ole option and did not work either

Already am up to date on office too

did detect and repair and reinstalled complete office to no avail

You're on Exchange 2003.  Are your emails stored on the server, or in a .pst file on your pc?

If a .pst file, you could be receiving this message because .pst file may be too large.  http://www.outlookpower.com/issues/issue200511/00001669001.html

nope...that is only at about 60 mb

Then it's certainly not that.  Does this user have admin permissions?

Local..yes

But rights have not changed since the error started to occur. Have been the same...just recently problem started occuring.

Nothing to my knowledge has been installed or uninstalled on pc that might have affected this..very weird

Yes, very odd.  I'm at a loss to explain why it's happening, but have one more suggested fix for you.  I've had this work on other issues when Office uninstall/reinstalls have failed:

Download and install Cleanup (http://www.stevengould.org/software/cleanup/download.html) and CCleaner (www.ccleaner.com).  

Uninstall Office.  Reboot.  Run the Cleanup utility.  Log off/back on.  Run the registry cleaner from CCleaner.  Reboot.  Reinstall Office and all updates.  Set back up the Outlook profile and see if it works.

Just a thought - is there a pst file for this user on the local pc?  If so, try a scanpst first, there may be something with the pst file.  http://www.slipstick.com/problems/scanpst.asp

No did not work with cleaners. I did find this though...can anyone explain and tell me where to find this and how to fix


SYMPTOMS
When you try to send a mail message with a Microsoft Excel for Windows routing slip attached, you will get the following error:
General mail failure. Close Excel, restart the mail system and try again.

Back to the top
CAUSE
You are addressing the message from the Personal Address Book (PAB) with the routing slip attached.

Back to the top
RESOLUTION
Address the message with a Microsoft Excel routing slip from the Postoffice Address List (POL) or the Global Address List (GAL).

You find the above info at:  http://support.microsoft.com/kb/135303

This fix does not apply to the versions of Excel, Outlook, or Exchange that you are running.  However, you can give it a try.  Open Outlook, click on your Address Book.  When it opens, On the right side near the top it will state "Show Names from the:".  What does it say below this?  Click on Tools -> Options.  A window titled Addressing pops up.  Under "Show this address list first:" select Global Address List (or you can select others and test).  

Well when I went to detect and repair I had it put everything back as default with specified option and did not save any personalized settings and it reset everything where it needs to be and it works. One of those things...cannot beleive complete uninstall of office and outlook did not work.

I am giving you the points michko for all the help you tried to give..thanks a bunch for the help in troubleshooting

You're welcome for the help and thank you for the points.

Hi Guys
I too am having the  "General mail failure. Quit Microsoft Office Excel, restart the mail system, and try again" error
I have done 'Detect and Repair'. I see that reinstalling hasnt helped others. and the user is not on exchange. pop is used.
So far no solutions have helped. Does anyone know how excel communicates with outlook. That may be a good place to start

Iteology - you are posting in a question that has been closed.  To ensure your question gets the attention from the largest number of experts, you should open a new question.

I found that you would need to make sure these files are in

%systemroot%\Windows\System32
and
%systemroot%\Windows\System32\dllcache

These are pertaining to Outlook Express and found if missing or corrupt then this error pops up.
You may be able to reinstall OE, but that has not been tested as we had built our own install cd minus all OE files.  So reinstalling OE may work as well, but make sure these files are in the prescribed location.  It may be best just to overwrite them with known good files.

Inetcomm.dll
Msoeacct.dll
Msoert2.dll
Msoe.dll
Msoeres.dll
Msimn.exe
Oeimport.dll
Oemiglib.dll
Oemig50.exe
Setup50.exe
Wab.exe
Wabfind.dll
Wabimp.dll
Wabmig.exe
Csapi3t1.dll
Directdb.dll
Wab32.dll
Wab32res.dll

installing office 2007's  SP2, and rebooting resolved this issue for us.

Try running the Microsoft office Diagnostics tool:

Start > Programs > Microsoft Office Tools

I ran it and the diagnositcs detected an issue and resolved it.  There wasn't a description what it resolved, but it worked.  

Give it a try.