We saw the same thing today.
Delete all saved credentials on the credentials manager on the user side and check if they are logged into office online in outlook.

When we did that, everything was sending as it should.

Upgraded to 8510 at the end of last week and i'm getting lots of reports of email stuck in Outlook outbox.
I have reports that most are in long threads with new recipients sometimes added.
Email addresses i notice show as "name" space <emailaddress> but some show in the same email as "name"<emailaddress> with no space between the name and address.
Last time we had this problem is was caused by some formatting issue in senders signature files.

I was forwarded one of these emails and sent a reply to the single sender and the email stuck in the outbox. I snipped most of the conversation leaving the last 2 and hit send and it went out.

Seems there is a formatting issue and it's not restricted to the email addresses but also in the html format of the message itself.

I've seen same. Assumed also formatting issues. New emails send fine. Replies are the issue. 

Have you tried 8517??

My clients need the ongoing threads/conversations as an audit so cannot delete previous quoted messages. Many users are just using Webmail and emails get sent but when they use Outlook it gets stuck in the outbox. Quite a few users are using Outlook and get quite upset when you tell them to reply to that email in webmail but your others you're ok to send in Outlook.
Is there a comment from support about this issue yet..? is it related to the MAPI not syncing problem?