When a signed and encrypted message is composed in Evolution, the MIME content of the EnvelopedData object is formatted with bare linefeeds (LFs). This causes proper MIME processing agents to fail. Bare LF is not valid MIME--all MIME messages (and e-mail in general) are required to use CRLFs as line endings. The outer message, where the EnvelopedData is base64 encoded, and the inner message inside the SignedData part, are properly CRLF encoded. It's just the layer in between.

See RFC 2633, sec. 3.1.1.

When an EnvelopedData (encrypted)-only message is composed, and when a SignedData (signed)-only message is composed, this is not a problem.

I narrowed the problem down to these lines in the trunk:

/evolution-data-server/camel/camel-smime-context.c

lines 1094 onward:
	/* FIXME: Canonicalise the input? */
	mem = (CamelStreamMem *)camel_stream_mem_new();
	camel_data_wrapper_write_to_stream((CamelDataWrapper *)ipart, (CamelStream *)mem);
	if (NSS_CMSEncoder_Update(enc, (gchar *) mem->buffer->data, mem->buffer->len) != SECSuccess) {

should probably read:
mem = (CamelStreamMem *)camel_stream_mem_new();
camel_cipher_canonical_to_stream(ipart, CAMEL_MIME_FILTER_CANON_CRLF, (CamelStream *)mem);
if (NSS_CMSEncoder_Update(enc, (gchar *) mem->buffer->data, mem->buffer->len) != SECSuccess) {

using camel_cipher_canonical_to_stream in "camel-cipher-context.c".

Unfortunately I have not been able to test this since I cannot build Evolution successfully yet. But, it looks simple enough to fix, especially since the FIXME comment says it all.