Копаясь в опциях Google Apps для своего домена (пришло уведомление, что меня перевели на новую версию этих самых аппсов), обнаружил интересную фичу, а именно, в Advanced есть подпись писем.
Делается все достаточно просто, через DKIM (DomainKeys Identified Mail). В домене добавляется TXT-запись .domain_key с ключом, этот же ключ Google добавляет в исходящие письма. На принимающей стороне сверяют ключ с тем, что указан в домене и при его несовпадении - отвергают письмо, как спам. Если честно, какое-то сомнительное средство, поскольку ничто не мешает этот ключ спамеру считывать при отправке писем от моего имени, например, но, допускаю, что я что-то не знаю об этой технологии, а лезть глубже пока не хочется. Опцию пока оставил включенной.