I doubt that Gmail and Hotmail ever send non-compliant messages. It would cause problems to many people.
I just tried sending messages to my mail server and see the messages in the mailbox directly without retrieving them with my mail client. The messages come well-formed as expected. Just take a look below. I just omitted some received headers to make them short.
The Hotmail message is plain text because I am using Firefox to access Hotmail. Still it has the Content-Type header.
It seems the problem is not really with Hotmail or Gmail. I suspect that you are not viewing messages as you should or your mail server is doing something odd to your messages.
Return-Path: <
[email protected]>
Message-ID: <
[email protected]>
Date: Mon, 25 Jun 2007 03:34:56 -0300
From: "Manuel Lemos" <
[email protected]>
To: 
[email protected]
Subject: Testing Gmail messages!
MIME-Version: 1.0
Content-Type: multipart/alternative; 
        boundary="----=_Part_5838_22942837.1182753296005"
------=_Part_5838_22942837.1182753296005
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
Testing Gmail messages!
------=_Part_5838_22942837.1182753296005
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
Testing Gmail messages!<br>
------=_Part_5838_22942837.1182753296005--
Return-Path: <
[email protected]>
Message-ID: <
[email protected]>
From: Manuel Lemos <
[email protected]>
To: <
[email protected]>
Subject: Testing Hotmail messages!
Date: Mon, 25 Jun 2007 07:50:05 +0100
Importance: Normal
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Return-Path: 
[email protected]
X-OriginalArrivalTime: 25 Jun 2007 06:50:06.0256 (UTC) FILETIME=[1072F300:01C7B6F5]
Testing Hotmail messages!