1) this issue will go away, but you need to be prepared for other things to stop working. Using a wildcard DNS record is bacically a general "and everything else I fortot to specifically add" option. If this has been used as a quick, lazy way to point many subdomains at one place, deleting it will stop those things from resolving to the right IP.
I would always recommend having a specific record for each subdomain you want to resolve as it avoids situations like this occurring.
2) outlook is not doing anything wrong. this is what it is designed to do. Every outlook 2007 tries to find an auto discover, its hard coded and cannot be disabled. Some of them are correctly failing to find one and giving up. a couple of your PCs seem to be having trouble but its not outlooks fault.
You may find that the users on the other PCs use some webapp on this IP address and may have permanently accepted or installed the certificate for the web based interface sometime in the past. These ones with a problem may not have done so and get the certificate issues.
Technically it isnt outlooks fault, it is the DNS/website's issue.