The question is a bit hard for me to decipher, but I am going to assume you are considering authenticating users by having the user present a username and password, and also having the user authenticate with a private key (client cert) that is stored on the user's device.
Short answer: yes, this is generally beneficial. If the user authenticates by both a client cert and a username/password pair, then yes, I would consider this two-factor authentication.
Even more important than whether it "counts as" two-factor authentication is whether it adds security, and whether it meets your security needs. Generally speaking, I would say that yes, this approach is useful and does add security, compared to just using username and password. You haven't provided enough information to assess whether it is adequate to your business needs, but I can share some thoughts on the strengths and weaknesses of this approach.
Security analysis. Generally speaking, requiring the user to authenticate using both a client cert and a username/password pair should be more secure than either one alone. I'll assume the client's private key is stored only on their device, and the user's password is not stored on the device. Here are some benefits:
Benefit: Security against social engineering. One weakness of passwords is that, since users know their own password, users can often be tricked into revealing their passwords, for instance by phishing, by spoofed email, by someone pretending to be from the IT help desk, or other forms of social engineering. Client certs address this risk: the benefit of the client cert is that the private key is a secret that the user does not know, so the user cannot be fooled into revealing it. An attacker may still be able to use social engineering to steal the user's password, but they won't find it easy to steal the user's private key, so they won't be able to get access to the user's account.
Benefit: Security against password guessing attacks. Another weakness of passwords is that users often choose poor passwords (which can be guessed through dictionary attacks). Also, users often reuse passwords on multiple sites, which means that a compromise of one site can negatively affect the security of the others. Client certs eliminate this problem: the private key is chosen randomly by a computer, and thus does not have problems with low entropy. Consequently, even if an attacker can guess the user's password, the attacker cannot gain access to the user's account.
Benefit: Security against lost devices. One shortcoming of client certs is that the private key is stored on the user's device. Thus, if the user's device is lost or stolen, the private key is compromised and the new possessor of the device may be able to access the user's account. Using a password in addition to a client cert addresses this threat. If the user's device is lost or stolen, the recipient of the device probably won't be able to access the user's account, because the recipient won't know the user's password (assuming the user did not choose a password that was totally terrible).
However, there are also some limitations and pitfalls with this approach which are worth being aware of.
Limitation: Does not defend against client-side malware. This form of two-factor authentication does not defend against malware or spyware on the user's device. Such malware can record the user's password and also grab a copy of the user's private key, thus capturing all credentials needed to access the user's account. So, if you are concerned about client-side malware, you will need to use some other approach to mitigate that threat.
Pitfall: Don't store the password. There is a pitfall with this approach. If you store the user's password on the user's device, then the password just becomes one more secret on the device; the security is then no better than just using a client cert. In particular, at that point, if the user's device is lost or stolen, all the information needed to access the user's account is present on the user's phone, so the user's account must be considered compromised. Therefore, if you are writing a custom client app, it is important that you avoid storing the user's password on the user's device. Similarly, if this is intended to be accessible over the web, you must ensure that the user's password is not stored in their browser password manager.
Caveat. One word of caution about my analysis. I am addressing the general concept of authenticating users with a combination of username/password plus client cert. I cannot speak to implementation details about Outlook, Active Directory, Exchange, ActiveSync, reverse proxies, or other aspects specific to the Windows environment, as I'm not familiar with those details. I can only analyze the general approach. If I'm missing relevant implementation details, then my conclusions may not apply to your situation.
