did you ever find a solution to this problem? We're experiencing the same issue. Everything goes well until the length of the subject passes 179 characters AND it includes the character § (haven't tried with any other character because I need to use this as separator for a 3rd party application). Below that length no problem, larger than 179 without § no problem.

Both SQL Server 2008 SP1 and SQL Server 2008 R2 SP1 seem to have this issue.

It looks like it's related to the combination Outlook-SQL Server-Exchange because I can send a mail from SQL Server to my Gmail account with the "bad" subject line and receive it correctly. Sending a mail from Outlook 2010 with the "bad" subject line to myself works fine again.