I've had mail sent via my own server rejected by gmail because of a missing Message-ID header. The 550 reject message was the standard "Unsolicited Mail detected" text, the same mail was accepted without causing any fuzz once the Message-ID was added.