Gmail uses both DKIM and DomainKeys, while Hotmail uses none

It sounds like your PHP scripts are not sending the mail using the local MTA, while your Outlook client is. It's that MTA that needs to apply the DKIM signature to each message before it passes to another organization's servers. So, check your PHP configuration and code.

Yahoo does not generate the lock/key icon if the mail is signed with DKIM but not with DomainKeys.

If you really want the lock/key icon, sign the mail with DomainKeys as well.

If you're using Sendmail or Postfix, dk-filter should do the job quite nicely. It runs as a milter.

If you use both DKIM and DK, make sure that the DK signature is performed first. The reason for this is that DK does not self-sign the header, and DKIM does. Having the DK signature signed by the DKIM signature therefore bypasses the problem of DK's lack of self signature.

Ie, if, for example you are using OpenDKIM to sign with DKIM, make sure that the mail is passed through dk-filter and then OpenDKIM.

All that said, other than the lock/key icon in the older version of Yahoo's UI, there's no advantage to using DK and DKIM when compared to just using DKIM.