This was a particularly odd issue, e-mails wouldn't display in the web browser when a plus sign was present in the subject line. This manifested on a Windows Server 2008 system with Exchange 2007.
The answer was actually on a TechNet blog dedicated to Entourage, thanks to Amir for the answer. It makes sense that it would affect Entourage and most likely Evolution as well, because both use OWA to manage data, rather than RPC.
Here's the fix...
1. Open Notepad
2. Go to File > Open, then type (or copy and paste) %windir%\System32\inetsrv\config\applicationHost.config in the File name: field and click Open
3. Locate the section titled (use Ctrl-F): <location path="Default Web Site/Exchange">
4. Under that section locate the </authentication> tag
5. Create a new line, indented the same, and add: <requestFiltering allowDoubleEscaping="true" />
6. Save and Exit Notepad
You don't have to restart the server or any services, it'll just work.