Gmail использует и DKIM и DomainKeys, в то время как Hotmail не использует ни один?

1. Для дополнительной проверки подлинности.
2. Если Вы собираетесь не торопиться, чтобы настроить один, почему бы не оба?
3. Спросите их.

Microsoft поддерживает Идентификатор отправителя - http://mail.live.com/mail/policies.aspx