Outlook shows certificate security warning in local LAN although certificate is only associated to IIS

Instead of using an HTTP proxy, I suggest you set up Network Address Translation, to move IP packets at the IP layer. This will pass through the SSL connection without decrypting it at the gateway PC, and eliminate the security warning. Basically Outlook is telling you that your gateway PC is trying to perform a man in the middle attack, which it basically is.

The way SSL (encrypted) connections work is, it's perfectly fine if someone is sitting between you and the server you're communicating with and is simply viewing the encrypted traffic. The protocol is designed to accommodate situations where other computers (trusted or not) can see your encrypted traffic. But if other computers can see your encrypted traffic, such as with an HTTP proxy, the protocol is immediately aware of that fact, and flags the connection as insecure.

You can set up Network Address Translation on the gateway PC (the one connected to the EvDO modem) using for example, Windows Internet Connection Sharing. This allows the other PCs connected to have a private IP address on a private subnet that all routes out to the EvDO modem eventually. It basically treats your gateway PC as a router. (Note the term "gateway" refers to a box that performs router and/or firewall-like functions in order to push traffic to and from another network; in this case, the public Internet).

Guides for setting up Windows ICS are exhorbitantly common, not only on SU but also in the Microsoft knowledge base and Windows help. Please explore some of the existing resources along these lines prior to asking for help on how to set up ICS.

Your research regarding certificates is correct. There IS technically a way to induce a silent man in the middle attack, by trusting a Root CA for which your freeproxy server has a signing key. I don't know if the actual freeproxy program is able to encrypt the traffic on a domain basis, but programs such as Burp definitely can, and there are existing guides out there explaining how to set it up (on Burp's site at portswigger.net).

However, ICS is a solution that is much more flexible and does not involve this configuration hassle, so I highly recommend it.

justhost is a hosting service provider and if you/your company host your mail services on their non-dedicated servers, this umbrella wildcard certificate will be used to secure the connection.

There's a limitation in SSL/TLS that the host name the client is connecting to is not revealed to the server until a secure socket has been established. This means the server must blindly supply a default certificate which is the "*.justhost.com" you saw.

Thus if you access the mail server through your company's alias domain, e.g. mail.company.com, a certificate subject mismatch will occur. You could use the following steps to find the correct domain to use:

1. ping your mail server to get its IP address
2. Use nslookup or whois to get the host name of the server. The host name should end with "justhost.com", which is covered by the wildcard certificate.
3. Replace the POP/IMAP server and SMTP server address with the host name in Outlook