"This message has not yet been submitted for delivery"

I am the admin of both, but I am extremely new to CRM and the company that did the implementation didn't provide any admin training.  That's why I am here looking for help from someone who knows Dynamics CRM.

It sounds as if your outgoing e-mail configuration needs to be checked from CRM.

You need to be aware of how CRM sends out e-mails. On the CRM user record, there are separate settings for Incoming and Outgoing mail. In your case, you need to check the outgoing e-mail setting - this can be Outlook or E-mail router.

If this is set to Outlook, then e-mails originated by the user will only ever get sent when the user has Outlook open(and the CRM Client for Outlook is installed). The user also has to set the CRM for Outlook to send e-mails via a setting in the CRM pull-down i(n Outlook) | Options.

If the user setting is E-mail Router, then the CRM E-mail Router needs to have been installed and configured. There is documentation on how to do this.  

Once you've checked which scenario applies to you, let me know if you need more help.

@feridun

Thanks for your reply.  Here is our current config:

In each user profile in CRM, both incoming and outgoing is set to CRM Client for Outlook.
In Outlook, uncer CRM->Options->E-mail tab, "Allow Microsoft Dynamics CRM to send e-mail using CRM for Outlook" is checked.

You said that "e-mails originated by the user will only ever get sent when the user has Outlook open".  This may be the problem I am having as a lot of our sales folks are on the road and only have Outlook open once a day or so.  The one question I have about that is that these e-mails are workflow generated (system generated) no?  So should the user settings be affecting them?  

If I change the system to use the E-mail router, how does this affect the usability of the system?  Our company operates with all users sending e-mail from Outlook and attaching the e-mail to CRM records when necessary using the 'Set Regarding' buttons in Outlook; they hardly ever send e-mail from within CRM itself.  If I switch to using the e-mail router, will they still be able to function this way?

Ok, then I am confused as to why there is even a setting for using CRM for Outlook for e-mail.  Why isn't E-mail router simply hard-coded into the system.  Where is the benefit to setting it to Outlook at all if everything works the same for the end user regardless of which you choose?

Because the e-mail router is an extra item to install and configure and for businesses that have only a few CRM users, using CRM for Outlook for e-mail is a very simple and quick way of getting going.

But you are right, for most businesses the best settings are:
Incoming Mail: Forward Mailbox  (all mails get sent to a central mail box for the E-mail Router to poll)
Outgoing Mail: Email Router

You might find this msdn blog article useful (also review the links near the bottom of the article):

http://blogs.msdn.com/crm/archive/2008/03/21/mscrm-v4-e-mail-configuring-for-a-small-business.aspx

That link was quite helpful.  One last question.  We don't do auto-tracking of e-mail (simply because many of our users receive a lot of e-mail that doesn't need to be tracked); instead we allow them to manually track using the Set Regarding feature as mentioned above.  Is it possible to leave Outlook as the Incoming mail method and use the e-mail router only for outgoing?